二叉搜索树java实现

顾名思义，二叉搜索树是一棵二叉树，每个节点就是一个对象，这个对象包含属性left、right和parent。left指向节点的左孩子，right指向节点的右孩子，parent指向节点的父节点（双亲）。如果某个孩子节点和父节点不存在，则相应的属性为null。根节点是树中唯一父节点指针为null的节点。

二叉搜索树中的关键字满足以下性质：

假设x是二叉搜索树中的一个节点，如果y是x的左子树中的一个节点，那么y.key ≤ x.key；如果y是x右子树中的一个节点，那么y.key ≥ x.key。

两棵二叉搜索树的示意图如下：

二叉搜索树支持查询、求最大值、最小值以及追加和删除等操作，其基于java的简单实现如下：

/**
 * 数据结构-二叉搜索树
 */
public class BinarySearchTree {

    /**
     * 树的根节点
     */
    private Node root;

    /**
     * 根据关键字搜索节点
     *
     * @param key 关键字
     * @return key所在的节点
     */
    public Node search(int key) {
        Node node = root;
        while (node != null && key != node.key) {
            // 如果key小于当前节点的key，则往左孩子节点找，否则往右孩子节点找
            if (key < node.key) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return node;
    }

    /**
     * 获取key最小的节点
     *
     * @return key最小的节点
     */
    public Node min() {
        return min(root);
    }

    /**
     * 获取以node为根的子树中key最小的节点
     *
     * @param node 子树根节点
     * @return 子树中key最小的节点
     */
    public Node min(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * 获取key最大的节点
     *
     * @return key最大的节点
     */
    public Node max() {
        return max(root);
    }

    /**
     * 获取以node为根的子树中key最大的节点
     *
     * @param node 子树根节点
     * @return 子树中key最大的节点
     */
    public Node max(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    /**
     * 向树中添加节点
     *
     * @param key 插入节点的key
     */
    public void add(int key) {
        Node node = root;
        Node temp = null;

        // 寻找合适的节点添加新节点
        while (node != null) {
            temp = node;
            if (key < node.key) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        Node newNode = new Node();
        newNode.parent = temp;
        newNode.key = key;
        if (temp == null) { // 该树上还没有节点
            root = newNode;
        } else if (key < temp.key) {
            temp.left = newNode;
        } else {
            temp.right = newNode;
        }
    }

    /**
     * 删除以key为关键字的节点
     *
     * @param key 关键字
     */
    public void delete(int key) {
        Node node = search(key);
        if (node.left == null) {
            transplant(node, node.right);
        } else if (node.right == null) {
            transplant(node, node.left);
        } else {
            Node min = min(node.right);
            if (!min.parent.equals(node)) {
                transplant(min, min.right);
                min.right = node.right;
                min.right.parent = min;
            } 
            transplant(node, min);
            min.left = node.left;
            min.left.parent = min;
        }
    }

    /**
     * 用node2为跟的子树替换node1为根的子树
     *
     * @param node1 子树1
     * @param node2 子树2
     */
    private void transplant(Node node1, Node node2) {
        // node1是根节点
        if (node1.parent == null) {
            root = node2;
        } else if (node1 == node1.parent.left) { // 如果node1是左孩子
            node1.parent.left = node2;
        } else { // 如果node1是右孩子
            node1.parent.right = node2;
        }
        if (node2 != null) {
            node2.parent = node1.parent;
        }
    }

    public Node getRoot() {
        return root;
    }

    /**
     * 树上的节点
     */
    public static class Node {
        /**
         * 节点关键字
         */
        private int key;

        /**
         * 节点的左孩子
         */
        private Node left;

        /**
         * 节点的右孩子
         */
        private Node right;

        /**
         * 节点的父节点
         */
        private Node parent;

        public int getKey() {
            return key;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        public Node getParent() {
            return parent;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return key == node.key && Objects.equals(left, node.left)
                    && Objects.equals(right, node.right) && Objects.equals(parent, node.parent);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key, left, right, parent);
        }
    }
}