二叉搜索树的增删改查

Binary Search Tree（BST）

/**
 * @author wz
 */
// 定义二叉搜索树的节点类
class TreeNode {
    int val; // 节点值
    TreeNode left; // 左子树
    TreeNode right; // 右子树

    // 构造函数
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 定义二叉搜索树类
public class BinarySearchTree {
    private TreeNode root; // 树的根节点

    // 构造函数
    public BinarySearchTree() {
        this.root = null;
    }

    // 插入节点
    public void insert(int val) {
        root = insertRec(root, val);
    }

    // 插入节点的递归函数
    private TreeNode insertRec(TreeNode root, int val) {
        // 如果当前节点为空，创建一个新节点并返回
        if (root == null) {
            root = new TreeNode(val);
            return root;
        }
        // 根据值的大小决定插入左子树还是右子树
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else if (val > root.val) {
            root.right = insertRec(root.right, val);
        }
        // 返回当前节点
        return root;
    }

    // 删除节点
    public void delete(int val) {
        root = deleteRec(root, val);
    }

    // 删除节点的递归函数
    private TreeNode deleteRec(TreeNode root, int val) {
        // 如果当前节点为空，直接返回
        if (root == null) {
            return root;
        }
        // 根据值的大小决定在左子树还是右子树删除节点
        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 minVal = root.val;
        while (root.left != null) {
            minVal = root.left.val;
            root = root.left;
        }
        return minVal;
    }

    // 查找节点
    public boolean search(int val) {
        return searchRec(root, val);
    }

    // 查找节点的递归函数
    private boolean searchRec(TreeNode root, int val) {
        // 如果当前节点为空，表示未找到
        if (root == null) {
            return false;
        }
        // 如果找到值，返回 true
        if (root.val == val) {
            return true;
        }
        // 根据值的大小决定在左子树还是右子树查找
        return val < root.val ? searchRec(root.left, val) : searchRec(root.right, val);
    }

    // 修改节点值
    public void update(int oldVal, int newVal) {
        delete(oldVal); // 删除旧值
        insert(newVal); // 插入新值
    }

    // 中序遍历
    public void inorder() {
        inorderRec(root);
    }

    // 中序遍历的递归函数
    private void inorderRec(TreeNode root) {
        if (root != null) {
            inorderRec(root.left); // 遍历左子树
            System.out.print(root.val + " "); // 访问当前节点
            inorderRec(root.right); // 遍历右子树
        }
    }

    // 主函数，用于测试上述功能
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        // 插入节点
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);
        bst.insert(55);

        // 中序遍历二叉搜索树
        System.out.println("Inorder traversal of the given tree:");
        bst.inorder();

        // 删除节点并进行中序遍历
        System.out.println("\n\nDelete 20:");
        bst.delete(55);
        bst.inorder();

        System.out.println("\n\nDelete 30:");
        bst.delete(30);
        bst.inorder();

        System.out.println("\n\nDelete 50:");
        bst.delete(50);
        bst.inorder();

        // 查找节点
        System.out.println("\n\nSearch 70:");
        System.out.println(bst.search(70));

        // 修改节点值并进行中序遍历
        System.out.println("\n\nUpdate 60 to 65:");
        bst.update(60, 65);
        bst.inorder();
    }
}