一颗二叉搜索树

二叉搜索树是一颗度为2的数，且左子树都不大于根节点，右子树都不小于根节点。
以下分步实现一个简单的二叉搜索树

节点
二叉搜索树上的节点保存着一个值value, 指向父节点的指针，以及两个指向左右兄弟的指针。简单的实现如下：

    public class Node {
        T value;
        Node parent;
        Node left;
        Node right;

        Node(T v, Node p, Node l, Node r) {
            this.value = v;
            this.parent = p;
            this.left = l;
            this.right = r;
        }
    }

查找操作

    // 在root上查找值为v节点
    public Node serach(Node root, T v) {
        if (root == null || root.value.compareTo(v) == 0)
            return root;
        // 在左子树上
        if (root.value.compareTo(v) > 0)
            return serach(root.left, v);
        else
            return serach(root.right, v);
    }

查找操作的逻辑如下：

如果v的值是在root节点上，那么就返回root。
如果v的值小于root节点上的key,那么在左子树上查找。
如果v的值大于root节点上的key,那么在右子树上查找。

最小节点和最大节点

    // 最小节点
    public Node minimum(Node root) {
        if (root == null)
            return root;
        while (root.left != null)
            root = root.left;
        return root;
    }

    // 最大节点
    public Node maxmum(Node root) {
        if (root == null)
            return root;
        while (root.right != null)
            root = root.right;
        return root;
    }

最小节点在最左的子树上，最大节点在最右子树上

前驱和后继节点

    // 后继节点
    public Node successor(Node n) {
        if (n == null)
            return n;
        if (n.right != null)
            return minimum(n.right);
        Node successor = n.parent;
        while (successor != null && n == successor.right) {
            successor = n;
            successor = successor.parent;
        }5t
        return successor;
    }

    // 前驱
    public Node predecessor(Node n) {
        if (n == null)
            return n;
        if (n.left != null)
            return maxmum(n.left);
        Node y = n.parent;
        while (y != null && n == y.right) {
            y = n;
            y = y.parent;
        }
        return y;
    }

如果一个节点有右子树，那么它的后继节点是右子树的最小节点。
如果没有右子树，且有后继节点，那么它的后继节点就是往上的第一个没有子树的父节点，如下图中的22的节点是24。 前驱节点与后继节点的逻辑相反

插入

    // 插入
    public Node insert(BinaryTree<T> tree, T v) {

        if (tree.root == null) {
            tree.root = new Node(v, null, null, null);
            return tree.root;
        }

        Node temp = tree.root;
        Node last = null;
        while (temp != null) {
            last = temp;
            if (temp.value.compareTo(v) > 0)
                last = temp.left;
            else
                last = temp.right;
        }

        Node newNode = new Node(v, last, null, null);
        if (last.value.compareTo(v) > 0)
            last.left = newNode;
        else
            last.right = newNode;
        return newNode;

    }

二叉搜索树的插入，如果插入的值比根小。在左子树上寻找插入的点。否则在右子树上插入。

删除
二叉搜索树的删除之后还需要保持二叉搜索树左子树不大于根节点，右子树不大于跟节点的特性。需要进行一些额外的操作。分几种情况讨论

1. 当删除的节点(15)仅有一颗右子树(16)，那么就用右子树代替要删除的节点
2. 当删除的节点(15)仅有一颗左子树(15), 那么就用左子树代替要删除的节点

3.当删除的节点(15)有2个子节点，且后继节点(17)没有子节点，那么用后继节点代替删除的节点
4. 当删除的节点(15)的后继节点(17)有一颗右子树(17.5)（一定是右子树而不是左子树，左子树会是删除节点的后继节点），则用右子树替换后继节点(17),再用后继节点替换删除节点(15)

    // 删除
    public void delete(BinaryTree<T> tree, Node z) {
        if (z.left == null)
            transplant(tree, z, z.right);
        else if (z.right == null)
            transplant(tree, z, z.left);
        else {
            Node y = minimum(z.right);
            if (y.parent != z) {
                transplant(tree, y, y.right);
                y.right = z.right;
                y.right.parent = y;
            }
            transplant(tree, z, y);
            y.left = z.left;
            y.left.parent = y;
        }
    }

// 子树交换,用子树v交换u
    private void transplant(BinaryTree<T> tree, Node u, Node v) {
        if (u.parent == null)
            tree.root = v;
        else if (u == u.parent.left)
            u.parent.left = v;
        else   
            u.parent.right = v;
        if (v != null)
            v.parent = u.parent;
    }

貌似在粗制滥造，为了写而写的。。。感觉非常不好~