Java 实现二叉查找树

二叉查找树（Binary Search Tree）是一种常见的数据结构，它的每个节点最多有两个子节点，左子节点的值小于父节点的值，右子节点的值大于父节点的值。Java 实现二叉查找树的代码如下：

public class BinarySearchTree {
    private Node root;

    private class Node {
        private int key;
        private Node left;
        private Node right;

        public Node(int key) {
            this.key = key;
        }
    }

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

    private Node insert(Node x, int key) {
        if (x == null) {
            return new Node(key);
        }
        if (key < x.key) {
            x.left = insert(x.left, key);
        } else if (key > x.key) {
            x.right = insert(x.right, key);
        }
        return x;
    }

    public boolean contains(int key) {
        return contains(root, key);
    }

    private boolean contains(Node x, int key) {
        if (x == null) {
            return false;
        }
        if (key == x.key) {
            return true;
        } else if (key < x.key) {
            return contains(x.left, key);
        } else {
            return contains(x.right, key);
        }
    }

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

    private Node delete(Node x, int key) {
        if (x == null) {
            return null;
        }
        if (key < x.key) {
            x.left = delete(x.left, key);
        } else if (key > x.key) {
            x.right = delete(x.right, key);
        } else {
            if (x.left == null) {
                return x.right;
            } else if (x.right == null) {
                return x.left;
            } else {
                Node t = x;
                x = min(t.right);
                x.right = deleteMin(t.right);
                x.left = t.left;
            }
        }
        return x;
    }

    private Node min(Node x) {
        if (x.left == null) {
            return x;
        } else {
            return min(x.left);
        }
    }

    private Node deleteMin(Node x) {
        if (x.left == null) {
            return x.right;
        }
        x.left = deleteMin(x.left);
        return x;
    }
}

这段代码实现了二叉查找树的插入、查找和删除操作。其中，插入操作使用递归实现，查找和删除操作也是递归实现的。