二叉搜索树(BST)完全指南：详解搜索、插入和删除操作 | 算法入门必备
在本教程中，我们将讨论二叉搜索树数据结构。我们将实现从二叉搜索树中搜索、插入和删除值的函数。我们将递归和迭代地实现这些操作。
二叉搜索树
二叉搜索树具有以下性质：
- 所有节点的左子节点的值总是小于父节点。
- 所有节点的右子节点的值总是大于父节点。
在接下来的章节中，我们将学习如何递归和迭代地搜索、插入和删除二叉搜索树。让我们首先创建我们的二叉树数据结构。
public class BinaryTree {
public TreeNode root;
public static class TreeNode {
public TreeNode left;
public TreeNode right;
public Object data;
public TreeNode(Object data) {
this.data = data;
left = right = null;
}
}
}
请注意，上述实现不是二叉搜索树，因为在向树中插入元素时没有任何限制。
以递归方式进行二叉搜索树搜索
以下的Java程序包含了一个用递归方式在二叉搜索树中查找值的函数。
public class SearchInsertRemoveFromTree {
public static void main(String[] args) {
/**
* 我们的示例二叉搜索树
* 10
* 5 20
* 4 8 15 25
*/
BinaryTree tree = new BinaryTree();
tree.root = new TreeNode(10);
tree.root.left = new TreeNode(5);
tree.root.right = new TreeNode(20);
tree.root.left.left = new TreeNode(4);
tree.root.left.right = new TreeNode(8);
tree.root.right.left = new TreeNode(15);
tree.root.right.right = new TreeNode(25);
System.out.println("搜索值2是否在树中？ " + searchRecursively(tree.root, 2));
System.out.println("搜索值10是否在树中？ " + searchRecursively(tree.root, 10));
}
public static boolean searchRecursively(TreeNode root, int value) {
if (root == null)
return false;
if ((int) root.data == value)
return true;
if (value < (int) root.data)
return searchRecursively(root.left, value);
else if (value > (int) root.data)
return searchRecursively(root.right, value);
return false;
}
}
输出是：
以迭代方式进行二叉搜索树搜索
为了逐步搜索，请使用以下方法替代：
public static boolean searchIteratively(TreeNode root, int value) {
while (root != null) {
if ((int) root.data == value)
return true;
if (value < (int) root.data)
root = root.left;
else
root = root.right;
}
return false;
}
让我们来看一下如何在二叉搜索树中插入一个新节点。
递归地进行二叉搜索树插入
public static TreeNode insertionRecursive(TreeNode root, int value) {
if (root == null)
return new TreeNode(value);
if (value < (int) root.data) {
root.left = insertionRecursive(root.left, value);
} else if (value > (int) root.data) {
root.right = insertionRecursive(root.right, value);
}
return root;
}
public static void printInorderTraversal(TreeNode root) {
if (root != null) {
printInorderTraversal(root.left);
System.out.print(root.data + " ");
printInorderTraversal(root.right);
}
}
在主方法中调用上述方法。
tree.root = insertionRecursive(tree.root, 24);
tree.root = insertionRecursive(tree.root, 2);
printInorderTraversal(tree.root);
这棵树以中序遍历的形式打印出来。
二叉搜索树迭代式插入
为了在二叉搜索树中迭代地插入一个节点，我们需要使用两个指针遍历树。
public static TreeNode insertionIterative(TreeNode root, int value) {
TreeNode current, parent;
TreeNode tempNode = new TreeNode(value);
if (root == null) {
root = tempNode;
return root;
} else {
current = root;
}
while (true) {
parent = current;
if (value < (int) current.data) {
current = current.left;
if (current == null) {
parent.left = tempNode;
return root;
}
} else if (value > (int) current.data) {
current = current.right;
if (current == null) {
parent.right = tempNode;
return root;
}
}
}
}
递归删除二叉搜索树中的元素
从二叉搜索树中移除一个元素比搜索和插入复杂一些，因为我们必须确保二叉搜索树的性质得以保留。要删除一个节点，我们首先需要搜索它。然后我们需要确定该节点是否有子节点。
- 如果没有子节点 – 直接删除。
- 如果只有一个子节点 – 将该子节点复制到要删除的节点位置。
- 如果有两个子节点 – 确定右子树中的下一个最高元素（中序后继）。用中序后继替换要删除的节点。删除中序后继的重复项。
可以通过找到节点右子树中的最小值来获得中序遍历的后继。
下面这个Java程序从二叉搜索树中删除元素
public static TreeNode deleteRecursively(TreeNode root, int value) {
if (root == null)
return root;
if (value < (int) root.data) {
root.left = deleteRecursively(root.left, value);
} else if (value > (int) root.data) {
root.right = deleteRecursively(root.right, value);
} else {
if (root.left == null) {
return root.right;
} else if (root.right == null)
return root.left;
root.data = inOrderSuccessor(root.right);
root.right = deleteRecursively(root.right, (int) root.data);
}
return root;
}
public static int inOrderSuccessor(TreeNode root) {
int minimum = (int) root.data;
while (root.left != null) {
minimum = (int) root.left.data;
root = root.left;
}
return minimum;
}
在主方法中调用上面的删除方法。
tree.root = deleteRecursively(tree.root, 4);
tree.root = deleteRecursively(tree.root, 20);
printInorderTraversal(tree.root);
输出结果是：2 5 8 10 15 24 25 让我们用迭代的方式做同样的事情。
二叉搜索树迭代式删除元素
public static TreeNode deleteNodeIteratively(TreeNode root, int value) {
TreeNode parent = null, current = root;
boolean hasLeft = false;
if (root == null)
return root;
while (current != null) {
if ((int) current.data == value) {
break;
}
parent = current;
if (value < (int) current.data) {
hasLeft = true;
current = current.left;
} else {
hasLeft = false;
current = current.right;
}
}
if (parent == null) {
return deleteNodeIteratively(current);
}
if (hasLeft) {
parent.left = deleteNodeIteratively(current);
} else {
parent.right = deleteNodeIteratively(current);
}
return root;
}
private static TreeNode deleteNodeIteratively(TreeNode node) {
if (node != null) {
if (node.left == null && node.right == null) {
return null;
}
if (node.left != null && node.right != null) {
TreeNode inOrderSuccessor = deleteInOrderSuccessorDuplicate(node);
node.data = inOrderSuccessor.data;
} else if (node.left != null) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
private static TreeNode deleteInOrderSuccessorDuplicate(TreeNode node) {
TreeNode parent = node;
node = node.right;
boolean rightChild = node.left == null;
while (node.left != null) {
parent = node;
node = node.left;
}
if (rightChild) {
parent.right = node.right;
} else {
parent.left = node.right;
}
node.right = null;
return node;
}
二叉搜索树操作的时间复杂度为O(h)，其中h是树的高度。
这样就结束了本教程。
您可以在我们的GitHub存储库中查看完整的代码和更多的数据结构和算法示例。
