掌握Java二叉搜索树（BST）从零开始构建高效查找结构

Java二叉搜索树的基本结构

首先，我们需要定义一个节点类 TreeNode，它包含数据、左子节点和右子节点：

class TreeNode {    int val;    TreeNode left;    TreeNode right;    public TreeNode(int val) {        this.val = val;        this.left = null;        this.right = null;    }}  

二叉搜索树的插入操作

插入操作是构建二叉搜索树的基础。我们从根节点开始，比较要插入的值与当前节点的大小，决定向左还是向右递归，直到找到空位置。

public class BinarySearchTree {    private TreeNode root;    // 插入方法（对外接口）    public void insert(int val) {        root = insertRec(root, val);    }    // 递归插入方法    private TreeNode insertRec(TreeNode node, int val) {        // 基准情况：如果当前节点为空，创建新节点        if (node == null) {            return new TreeNode(val);        }        // 如果值小于当前节点，插入左子树        if (val < node.val) {            node.left = insertRec(node.left, val);        }        // 如果值大于当前节点，插入右子树        else if (val > node.val) {            node.right = insertRec(node.right, val);        }        // 如果值相等，通常不插入重复值（根据需求可调整）        return node;    }}  

查找操作

查找某个值是否存在于树中，逻辑与插入类似：

public boolean search(int val) {    return searchRec(root, val);}private boolean searchRec(TreeNode node, int val) {    if (node == null) {        return false; // 未找到    }    if (val == node.val) {        return true; // 找到    }    if (val < node.val) {        return searchRec(node.left, val);    } else {        return searchRec(node.right, val);    }}  

删除操作（较复杂）

删除节点有三种情况：

1. 要删除的节点是叶子节点（无子节点）——直接删除；
2. 有一个子节点——用子节点替代它；
3. 有两个子节点——找到中序后继（右子树中的最小值）替换，并删除后继节点。

public void delete(int val) {    root = deleteRec(root, val);}private TreeNode deleteRec(TreeNode node, int val) {    if (node == null) return null;    if (val < node.val) {        node.left = deleteRec(node.left, val);    } else if (val > node.val) {        node.right = deleteRec(node.right, val);    } else {        // 找到要删除的节点        if (node.left == null) return node.right;        if (node.right == null) return node.left;        // 有两个子节点：找右子树的最小值（中序后继）        TreeNode successor = findMin(node.right);        node.val = successor.val;        node.right = deleteRec(node.right, successor.val);    }    return node;}private TreeNode findMin(TreeNode node) {    while (node.left != null) {        node = node.left;    }    return node;}  

完整使用示例

public class Main {    public static void main(String[] args) {        BinarySearchTree bst = new BinarySearchTree();        bst.insert(50);        bst.insert(30);        bst.insert(70);        bst.insert(20);        bst.insert(40);        System.out.println(bst.search(30)); // true        System.out.println(bst.search(25)); // false        bst.delete(30);        System.out.println(bst.search(30)); // false    }}  

总结

通过本教程，你已经掌握了如何用 Java 实现一个完整的二叉搜索树，包括插入、查找和删除操作。这是学习更高级数据结构（如 AVL 树、红黑树）的基础。记住，Java二叉搜索树 的平均时间复杂度为 O(log n)，但在最坏情况下（树退化为链表）会变成 O(n)。因此，在实际应用中常使用自平衡二叉搜索树来保证性能。

希望这篇 Java数据结构教程 能帮助你理解 二叉搜索树插入删除 的核心逻辑。动手写一写代码，你会掌握得更牢固！