Java怎么实现二叉查找树的增删查

二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下性质：

• 对于树中的每个节点，其左子树中的所有节点的值都小于该节点的值。
• 对于树中的每个节点，其右子树中的所有节点的值都大于该节点的值。
• 左右子树也分别是二叉查找树。

二叉查找树的主要操作包括插入、删除和查找。本文将介绍如何在Java中实现这些操作。

1. 二叉查找树的节点定义

首先，我们需要定义一个二叉查找树的节点类。每个节点包含一个值、一个左子节点和一个右子节点。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

2. 插入操作

插入操作的目标是将一个新节点插入到二叉查找树中，同时保持二叉查找树的性质。

class BST {
    private TreeNode root;

    public BST() {
        this.root = null;
    }

    public void insert(int val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else if (val > root.val) {
            root.right = insertRec(root.right, val);
        }

        return root;
    }
}

插入操作的解释

• 如果树为空，则创建一个新节点并将其作为根节点。
• 如果插入的值小于当前节点的值，则递归地在左子树中插入。
• 如果插入的值大于当前节点的值，则递归地在右子树中插入。
• 如果插入的值等于当前节点的值，则不做任何操作（假设树中不允许有重复值）。

3. 查找操作

查找操作的目标是在二叉查找树中查找一个特定的值。

public boolean search(int val) {
    return searchRec(root, val);
}

private boolean searchRec(TreeNode root, int val) {
    if (root == null) {
        return false;
    }

    if (val == root.val) {
        return true;
    } else if (val < root.val) {
        return searchRec(root.left, val);
    } else {
        return searchRec(root.right, val);
    }
}

查找操作的解释

• 如果树为空，则返回false，表示未找到。
• 如果当前节点的值等于要查找的值，则返回true。
• 如果要查找的值小于当前节点的值，则递归地在左子树中查找。
• 如果要查找的值大于当前节点的值，则递归地在右子树中查找。

4. 删除操作

删除操作的目标是从二叉查找树中删除一个节点，同时保持二叉查找树的性质。

public void delete(int val) {
    root = deleteRec(root, val);
}

private TreeNode deleteRec(TreeNode root, int val) {
    if (root == null) {
        return null;
    }

    if (val < root.val) {
        root.left = deleteRec(root.left, val);
    } else if (val > root.val) {
        root.right = deleteRec(root.right, val);
    } else {
        // 节点只有一个子节点或没有子节点
        if (root.left == null) {
            return root.right;
        } else if (root.right == null) {
            return root.left;
        }

        // 节点有两个子节点：找到右子树中的最小节点
        root.val = minValue(root.right);

        // 删除右子树中的最小节点
        root.right = deleteRec(root.right, root.val);
    }

    return root;
}

private int minValue(TreeNode root) {
    int minv = root.val;
    while (root.left != null) {
        minv = root.left.val;
        root = root.left;
    }
    return minv;
}

删除操作的解释

• 如果要删除的节点没有子节点，则直接删除该节点。
• 如果要删除的节点只有一个子节点，则用其子节点替换该节点。
• 如果要删除的节点有两个子节点，则找到右子树中的最小节点（即中序遍历的下一个节点），用该节点的值替换要删除的节点的值，然后删除右子树中的最小节点。

5. 完整代码示例

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

class BST {
    private TreeNode root;

    public BST() {
        this.root = null;
    }

    public void insert(int val) {
        root = insertRec(root, val);
    }

    private TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else if (val > root.val) {
            root.right = insertRec(root.right, val);
        }

        return root;
    }

    public boolean search(int val) {
        return searchRec(root, val);
    }

    private boolean searchRec(TreeNode root, int val) {
        if (root == null) {
            return false;
        }

        if (val == root.val) {
            return true;
        } else if (val < root.val) {
            return searchRec(root.left, val);
        } else {
            return searchRec(root.right, val);
        }
    }

    public void delete(int val) {
        root = deleteRec(root, val);
    }

    private TreeNode deleteRec(TreeNode root, int val) {
        if (root == null) {
            return null;
        }

        if (val < root.val) {
            root.left = deleteRec(root.left, val);
        } else if (val > root.val) {
            root.right = deleteRec(root.right, val);
        } else {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }

            root.val = minValue(root.right);

            root.right = deleteRec(root.right, root.val);
        }

        return root;
    }

    private int minValue(TreeNode root) {
        int minv = root.val;
        while (root.left != null) {
            minv = root.left.val;
            root = root.left;
        }
        return minv;
    }
}

public class Main {
    public static void main(String[] args) {
        BST bst = new BST();
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        System.out.println("查找20: " + bst.search(20)); // true
        System.out.println("查找90: " + bst.search(90)); // false

        bst.delete(20);
        System.out.println("删除20后查找20: " + bst.search(20)); // false

        bst.delete(30);
        System.out.println("删除30后查找30: " + bst.search(30)); // false

        bst.delete(50);
        System.out.println("删除50后查找50: " + bst.search(50)); // false
    }
}

6. 总结

本文介绍了如何在Java中实现二叉查找树的插入、查找和删除操作。二叉查找树是一种高效的数据结构，适用于需要频繁查找、插入和删除操作的场景。通过递归的方式，我们可以简洁地实现这些操作。希望本文对你理解二叉查找树的实现有所帮助。