东莞建设工程交易中心网站,上海专业网站建设公司电话,网站的连接二维码怎么做,seo培训班文章目录 二叉查找树一#xff0c;概述二#xff0c;添加数据三#xff0c;删除数据 二叉查找树
一#xff0c;概述
二叉查找树#xff0c;也称为二叉搜索树#xff0c;是一种特殊的二叉树#xff0c;它或者是一颗空树#xff0c;或者具有以下性质#xff1a;对于每… 文章目录 二叉查找树一概述二添加数据三删除数据 二叉查找树
一概述
二叉查找树也称为二叉搜索树是一种特殊的二叉树它或者是一颗空树或者具有以下性质对于每个非空节点其左子树中所有节点的值都小于该节点的值而右子树中所有节点的值都大于该节点的值。这种特性使得在二叉查找树中查找一个特定的值变得相对简单和高效。
二叉查找树的查找操作如下
从根节点开始查找。如果当前节点为空说明查找失败返回NULL。如果当前节点的值等于要查找的值说明查找成功返回当前节点。如果要查找的值小于当前节点的值则在左子树中继续查找。如果要查找的值大于当前节点的值则在右子树中继续查找。
在二叉查找树中每个节点的左子树和右子树的高度最多相差1因此二叉查找树的查找时间复杂度是O(log n)其中n是树中节点的数量。在最坏的情况下当树完全不平衡时可能退化成O(n)的时间复杂度。为了保持二叉查找树的效率通常会使用一些平衡的策略如AVL树和红黑树。
总的来说二叉查找树是一种常见的数据结构它具有很好的查找性能但是需要注意平衡的问题以避免效率的降低。
简介
二叉查找树是一种自我平衡的二叉树它的中序遍历会得到一个升序的序列。二叉查找树的每个节点都包含一个键和一个值其中键用于保持树的排序而值则可以是任何类型的数据。二叉查找树的主要操作包括插入、查找和删除。
图示
以下是一个简单的二叉查找树的图示 50/ \30 70/ \ / \10 40 60 80在这个二叉查找树中每个节点的键都大于其左子树中所有节点的键且小于其右子树中所有节点的键。
示例
以下是一个在Java中实现二叉查找树的简单示例
public class BinarySearchTree {class Node {int key;Node left, right;public Node(int item) {key item;left right null;}}Node root;BinarySearchTree(int key) {root new Node(key);}BinarySearchTree() {root null;}void insert(int key) {root insertRec(root, key);}Node insertRec(Node root, int key) {if (root null) {root new Node(key);return root;}if (key root.key) {root.left insertRec(root.left, key);} else if (key root.key) {root.right insertRec(root.right, key);}return root;}void inorder() {inorderRec(root);}void inorderRec(Node root) {if (root ! null) {inorderRec(root.left);System.out.println(root.key);inorderRec(root.right);}}
}在这个示例中定义了一个内部类Node来表示二叉查找树的节点。每个节点都有一个键key和两个子节点left和right。还定义了两个方法insert和inorder。insert方法用于向二叉查找树中插入一个新的节点而inorder方法则用于按中序遍历顺序打印出树中的所有节点的键。
二添加数据
在Java中二叉查找树Binary Search Tree是一种常见的数据结构。在二叉查找树中每个节点包含一个关键字和两个指向其子树的链接。树也必须满足二叉查找树性质左子树上的所有关键字都小于其根节点的关键字右子树上的所有关键字都大于其根节点的关键字。
下面是一个简单的Java类表示一个二叉查找树节点
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val x;}
}然后可以创建一个二叉查找树的类并实现添加数据的方法
public class BinarySearchTree {private TreeNode root;public BinarySearchTree() {root null;}public void add(int value) {root addRecursive(root, value);}private TreeNode addRecursive(TreeNode current, int value) {if (current null) {return new TreeNode(value);}if (value current.val) {current.left addRecursive(current.left, value);} else if (value current.val) {current.right addRecursive(current.right, value);} else {// value already exists in the tree, do nothingreturn current;}return current;}
}在这个类中使用了递归方法addRecursive来找到应该插入新节点的位置。如果树为空就在根节点插入新值。如果新值小于当前节点的值将其插入到左子树如果新值大于当前节点的值将其插入到右子树。如果新值已经存在于树中什么也不做。
三删除数据
在Java中二叉查找树Binary Search Tree是一种常见的数据结构。在二叉查找树中每个节点包含一个关键字和两个指向其子树的链接。树也必须满足二叉查找树性质左子树上的所有关键字都小于其根节点的关键字右子树上的所有关键字都大于其根节点的关键字。
下面是一个简单的Java类表示一个二叉查找树节点
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val x;}
}然后可以创建一个二叉查找树的类并实现删除数据的方法
public class BinarySearchTree {private TreeNode root;public BinarySearchTree() {root null;}public void remove(int value) {root removeRecursive(root, value);}private TreeNode removeRecursive(TreeNode current, int value) {if (current null) {return null;}if (value current.val) {// Node with the given value found, remove it from the tree.if (current.left null current.right null) {return null;} else if (current.left null) {return current.right;} else if (current.right null) {return current.left;} else {// Find the minimum value in the right subtree and replace it with the current nodes value.TreeNode minNode findMin(current.right);current.val minNode.val;current.right removeRecursive(current.right, minNode.val);return current;}} else if (value current.val) {current.left removeRecursive(current.left, value);return current;} else {current.right removeRecursive(current.right, value);return current;}}private TreeNode findMin(TreeNode node) {while (node.left ! null) {node node.left;}return node;}
}在这个类中使用了递归方法removeRecursive来找到应该删除节点的位置。如果要删除的节点没有子节点直接返回null。如果要删除的节点只有一个子节点将这个子节点返回作为新的节点。如果要删除的节点有两个子节点找到右子树中的最小节点用它替换要删除的节点然后在右子树中递归删除这个最小节点。
