编码实现
完整二叉搜索树实现
public class BinarySearchTree {
private TreeNode root;
private class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// 插入新节点
public void insert(int value) {
root = insertRecursive(root, value);
}
private TreeNode insertRecursive(TreeNode current, int value) {
if (current == null) {
return new TreeNode(value);
}
if (value < current.value) {
current.left = insertRecursive(current.left, value);
} else if (value > current.value) {
current.right = insertRecursive(current.right, value);
}
return current;
}
}
遍历方法实现
递归遍历方法
public class BinarySearchTree {
// 中序遍历
public void inOrderTraversal() {
inOrderTraversal(root);
}
private void inOrderTraversal(TreeNode node) {
if (node!= null) {
inOrderTraversal(node.left);
System.out.print(node.value + " ");
inOrderTraversal(node.right);
}
}
// 前序遍历
public void preOrderTraversal() {
preOrderTraversal(root);
}
private void preOrderTraversal(TreeNode node) {
if (node!= null) {
System.out.print(node.value + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
// 后序遍历
public void postOrderTraversal() {
postOrderTraversal(root);
}
private void postOrderTraversal(TreeNode node) {
if (node!= null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(node.value + " ");
}
}
}
迭代遍历实现
import java.util.Stack;
public class BinarySearchTree {
// 迭代中序遍历
public void iterativeInOrder() {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current!= null ||!stack.isEmpty()) {
while (current!= null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
System.out.print(current.value + " ");
current = current.right;
}
}
// 迭代前序遍历
public void iterativePreOrder() {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.value + " ");
if (node.right!= null) {
stack.push(node.right);
}
if (node.left!= null) {
stack.push(node.left);
}
}
}
}
搜索和删除方法
public class BinarySearchTree {
// 搜索值
public boolean search(int value) {
return searchRecursive(root, value);
}
private boolean searchRecursive(TreeNode current, int value) {
if (current == null) {
return false;
}
if (value == current.value) {
return true;
}
return value < current.value
? searchRecursive(current.left, value)
: searchRecursive(current.right, value);
}
// 删除节点
public void delete(int value) {
root = deleteRecursive(root, value);
}
private TreeNode deleteRecursive(TreeNode current, int value) {
if (current == null) {
return null;
}
if (value == current.value) {
// 没有子节点的节点
if (current.left == null && current.right == null) {
return null;
}
// 只有一个子节点的节点
if (current.right == null) {
return current.left;
}
if (current.left == null) {
return current.right;
}
// 有两个子节点的节点
int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;
}
if (value < current.value) {
current.left = deleteRecursive(current.left, value);
return current;
}
current.right = deleteRecursive(current.right, value);
return current;
}
private int findSmallestValue(TreeNode root) {
return root.left == null? root.value : findSmallestValue(root.left);
}
}
树的复杂度分析
| 操作 |
平均情况 |
最坏情况 |
| 搜索 |
O(log n) |
O(n) |
| 插入 |
O(log n) |
O(n) |
| 删除 |
O(log n) |
O(n) |
最佳实践
- 始终平衡你的树以保持O(log n)的操作
- 对于大树使用迭代方法以防止栈溢出
- LabEx建议练习这些实现以掌握树遍历技术
