在本教程中，我们将讨论二叉搜索树数据结构。我们将实现在二叉搜索树中搜索、插入和删除值的函数。我们将以递归和迭代的方式实现这些操作。
二叉搜索树
二叉搜索树具有以下属性：
- 所有节点都应使左子节点始终小于父节点。
- 右子节点始终大于父节点。
在下面的部分中，我们将看到如何在BST中递归地和迭代地搜索、插入和删除。让我们先创建一个二叉树数据结构：
1public class BinaryTree {
2
3 public TreeNode root;
4
5 public static class TreeNode {
6
7 public TreeNode left;
8 public TreeNode right;
9 public Object data;
10
11 public TreeNode(Object data) {
12 this.data = data;
13 left = right = null;
14 }
15 }
16}
请注意，上面的实现不是二叉搜索树，因为在向树中插入元素方面没有限制。
BST递归搜索
下面的Java程序包含递归搜索BST中的值的函数。
1public class SearchInsertRemoveFromTree {
2
3 public static void main(String[] args) {
4
5 /**
6 * Our Example Binary Search Tree
7 * 10
8 * 5 20
9 * 4 8 15 25
10 */
11
12 BinaryTree tree = new BinaryTree();
13 tree.root = new TreeNode(10);
14 tree.root.left = new TreeNode(5);
15 tree.root.right = new TreeNode(20);
16 tree.root.left.left = new TreeNode(4);
17 tree.root.left.right = new TreeNode(8);
18 tree.root.right.left = new TreeNode(15);
19 tree.root.right.right = new TreeNode(25);
20
21 System.out.println("Search Value 2 is in tree? " + searchRecursively(tree.root, 2));
22 System.out.println("Search Value 10 in tree? " + searchRecursively(tree.root, 10));
23 }
24
25 public static boolean searchRecursively(TreeNode root, int value) {
26
27 if (root == null)
28 return false;
29
30 if ((int) root.data == value)
31 return true;
32
33 if (value < (int) root.data)
34 return searchRecursively(root.left, value);
35
36 else if (value > (int) root.data)
37 return searchRecursively(root.right, value);
38
39 return false;
40 }
41}
输出为：
BST迭代搜索
要迭代搜索，请改用以下方法：
1public static boolean searchIteratively(TreeNode root, int value) {
2
3 while (root != null) {
4 if ((int) root.data == value)
5 return true;
6
7 if (value < (int) root.data)
8 root = root.left;
9
10 else
11 root = root.right;
12 }
13
14 return false;
15 }
让我们看看如何在二叉搜索树中插入新节点。
BST递归插入
1public static TreeNode insertionRecursive(TreeNode root, int value) {
2
3 if (root == null)
4 return new TreeNode(value);
5
6 if (value < (int) root.data) {
7 root.left = insertionRecursive(root.left, value);
8 } else if (value > (int) root.data) {
9 root.right = insertionRecursive(root.right, value);
10 }
11
12 return root;
13
14 }
15
16public static void printInorderTraversal(TreeNode root) {
17 if (root != null) {
18 printInorderTraversal(root.left);
19 System.out.print(root.data + " ");
20 printInorderTraversal(root.right);
21 }
22 }
在Main方法中调用上述方法：
1tree.root = insertionRecursive(tree.root, 24);
2tree.root = insertionRecursive(tree.root, 2);
3printInorderTraversal(tree.root);
树以顺序遍历的形式打印。
BST插入迭代
要在BST树中迭代地插入Node，我们需要使用两个指针遍历树。
1public static TreeNode insertionIterative(TreeNode root, int value) {
2
3 TreeNode current, parent;
4
5 TreeNode tempNode = new TreeNode(value);
6
7 if (root == null) {
8 root = tempNode;
9 return root;
10 } else {
11 current = root;
12 }
13
14 while (true) {
15 parent = current;
16
17 if (value < (int) current.data) {
18 current = current.left;
19 if (current == null) {
20 parent.left = tempNode;
21 return root;
22 }
23
24 } else if (value > (int) current.data) {
25 current = current.right;
26
27 if (current == null) {
28 parent.right = tempNode;
29 return root;
30 }
31 }
32
33 }
34 }
BST递归移除元素
从BST中删除一个元素比搜索和插入要复杂一些，因为我们必须确保BST属性是保守的。要删除一个节点，我们首先需要搜索它，然后我们需要确定该节点是否有子节点。
- 如果没有子代 -删除即可。
- 如果是单个子节点 -将该子节点复制到节点。
- 如果有两个子元素 -确定右子树中的下一个最高元素(顺序后继元素)。将要删除的节点替换为有序后续节点。删除订单后续副本。
中序后继可以通过寻找节点的右子节点中的最小值来获得。
下面的Java程序从BST中删除元素：
1public static TreeNode deleteRecursively(TreeNode root, int value) {
2
3 if (root == null)
4 return root;
5
6 if (value < (int) root.data) {
7 root.left = deleteRecursively(root.left, value);
8 } else if (value > (int) root.data) {
9 root.right = deleteRecursively(root.right, value);
10 } else {
11
12 if (root.left == null) {
13 return root.right;
14 } else if (root.right == null)
15 return root.left;
16
17 root.data = inOrderSuccessor(root.right);
18 root.right = deleteRecursively(root.right, (int) root.data);
19 }
20
21 return root;
22
23 }
24
25 public static int inOrderSuccessor(TreeNode root) {
26 int minimum = (int) root.data;
27 while (root.left != null) {
28 minimum = (int) root.left.data;
29 root = root.left;
30 }
31 return minimum;
32 }
在main方法中调用上述删除方法：
1tree.root = deleteRecursively(tree.root, 4);
2tree.root = deleteRecursively(tree.root, 20);
3printInorderTraversal(tree.root);
输出为：2 5 8 10 15 24 25 让我们迭代地做同样的事情。
BST迭代移除元素
1public static TreeNode deleteNodeIteratively(TreeNode root, int value) {
2 TreeNode parent = null, current = root;
3 boolean hasLeft = false;
4
5 if (root == null)
6 return root;
7
8 while (current != null) {
9 if ((int) current.data == value) {
10 break;
11 }
12
13 parent = current;
14 if (value < (int) current.data) {
15 hasLeft = true;
16 current = current.left;
17 } else {
18 hasLeft = false;
19 current = current.right;
20 }
21 }
22
23 if (parent == null) {
24 return deleteNodeIteratively(current);
25 }
26
27 if (hasLeft) {
28 parent.left = deleteNodeIteratively(current);
29 } else {
30 parent.right = deleteNodeIteratively(current);
31 }
32
33 return root;
34 }
35
36 private static TreeNode deleteNodeIteratively(TreeNode node) {
37
38 if (node != null) {
39 if (node.left == null && node.right == null) {
40 return null;
41 }
42
43 if (node.left != null && node.right != null) {
44 TreeNode inOrderSuccessor = deleteInOrderSuccessorDuplicate(node);
45 node.data = inOrderSuccessor.data;
46 } else if (node.left != null) {
47 node = node.left;
48 } else {
49 node = node.right;
50 }
51 }
52
53 return node;
54 }
55
56 private static TreeNode deleteInOrderSuccessorDuplicate(TreeNode node) {
57 TreeNode parent = node;
58 node = node.right;
59 boolean rightChild = node.left == null;
60
61 while (node.left != null) {
62 parent = node;
63 node = node.left;
64 }
65
66 if (rightChild) {
67 parent.right = node.right;
68 } else {
69 parent.left = node.right;
70 }
71
72 node.right = null;
73 return node;
74 }
BST运算的时间复杂度为O(H)。H是树的高度。
这就是本教程的结束。
您可以从我们的giHub Repository.]签出完整的代码和更多DS和算法示例