Java代码实现二叉排序树

二叉排序树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下条件：

- 左子树中的所有节点的值均小于根节点的值；
- 右子树中的所有节点的值均大于根节点的值；
- 左右子树也分别为二叉排序树。

Java代码实现二叉排序树：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BinarySearchTree {
    private TreeNode root;  // 根节点

    // 插入节点
    public void insert(int val) {
        if (root == null) {  // 如果根节点为空，直接插入
            root = new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        while (cur != null) {
            if (val < cur.val) {  // 小于当前节点，往左子树找
                if (cur.left == null) {
                    cur.left = new TreeNode(val);
                    return;
                }
                cur = cur.left;
            } else {  // 大于等于当前节点，往右子树找
                if (cur.right == null) {
                    cur.right = new TreeNode(val);
                    return;
                }
                cur = cur.right;
            }
        }
    }

    // 查找节点
    public boolean search(int val) {
        TreeNode cur = root;
        while (cur != null) {
            if (val == cur.val) {
                return true;
            } else if (val < cur.val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return false;
    }

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

    private TreeNode deleteNode(TreeNode root, int val) {
        if (root == null) {  // 没有找到要删除的节点
            return null;
        }
        if (val < root.val) {  // 继续在左子树中删除
            root.left = deleteNode(root.left, val);
        } else if (val > root.val) {  // 继续在右子树中删除
            root.right = deleteNode(root.right, val);
        } else {  // 找到要删除的节点
            if (root.left == null) {  // 左子树为空或者左右子树都为空
                return root.right;
            } else if (root.right == null) {  // 右子树为空
                return root.left;
            } else {  // 左右子树都不为空
                TreeNode minNode = findMin(root.right);  // 找到右子树中最小的节点
                root.val = minNode.val;  // 用右子树中最小的节点代替要删除的节点
                root.right = deleteNode(root.right, minNode.val);  // 删除右子树中最小的节点
            }
        }
        return root;
    }

    // 找到以root为根的二叉搜索树的最小节点
    private TreeNode findMin(TreeNode root) {
        while (root.left != null) {
            root = root.left;
        }
        return root;
    }
}

以上代码实现了二叉排序树的基本操作：插入节点、查找节点和删除节点。其中删除节点需要考虑三种情况：左子树为空、右子树为空和左右子树都不为空。对于第三种情况，需要在右子树中找到最小的节点代替要删除的节点，然后再删除右子树中最小的节点。