Tree 二叉搜索树

每个节点最多两个子节点，其中左边节点的值小于该节点的值，右边节点的值大于该节点的值。为了简便起见，该二叉树装入的数据为整数，且不允许有重复的关键字值。

编程中为了简便，采用了递归算法，运算时会带来额外的开销，如果能将相应的算法替换为迭代，则更为有效。删除的算法相应复杂一些，但也可以承受。

API
add：将数加入树
remove：从树中删除指定的节点
contains：树中是否包含指定的数
ordinal：从小到大遍历打印数（测试只用）
max：查找最大值
min：查找最小值
其中Node类是辅助类，为了简单没有写标准的 get，set方法。

因为该树没有自我保持平衡的能力，因此对于随机插入的数据，效果较好，对于有局部生降序特征的插入序列，则会失去平衡，极端状况下，树退化成链表。关于平衡树请参见（Tree2-3-4 ，红黑树 ,Tree-2-3 )
Tree的main函数仅为测试之用。

class Node {

    private int value;

    private Node left;

    private Node right;



    Node(int value) {

        this.value = value;

    }



    int value() {

        return value;

    }



    void left(Node left) {

        this.left = left;

    }



    void right(Node right) {

        this.right = right;

    }



    Node left() {

        return left;

    }



    Node right() {

        return right;

    }

}



class Tree {

    private Node root;

   

    void add(int value) {

        Node node = new Node(value);   

        if(root == null) root = node;

        else add(root,node);

    }



    private void add(Node current, Node node) {

        if(node.value() < current.value()) {

            if(current.left() == null) current.left(node);

            else add(current.left(), node);

        } else if(node.value() > current.value()) {

            if(current.right() == null) current.right(node);

            else add(current.right(), node);

        }

    }



    boolean contains(int value) {

        if(root == null) return false;

        else return contains(root,value);

    }



    private boolean contains(Node current, int value) {

        if(current == null) return false;

        if(current.value() == value) return true;

        if(value < current.value()) return contains(current.left(),value);

        else return contains(current.right(),value);

    }



    void remove(int value) {

        remove(null,root,value);

    }



    private void remove(Node parent, Node current, int value) {

        if(current == null) return;

        if(current.value() == value) {

            Node node;

            if(current.left() == null && current.right() ==  null) node = null;

            else if (current.left() != null && current.right() == null) node = current.left();

            else if (current.right() != null && current.left() == null) node = current.right();

            else {

                node = removeMin(current,current.right());

                node.left(current.left());

                node.right(current.right());

            }

            if(parent == null) root = node;

            else if(parent.left() == current) parent.left(node);

            else parent.right(node);

        } else if(value < current.value()) remove(current,current.left(),value);

        else remove(current,current.right(),value);

    }



    private Node removeMin(Node parent, Node current) {

        if(current.left() != null) return removeMin(current,current.left());

        else {

            if(parent.left() == current) parent.left(current.right());

            else parent.right(current.right());

            return current;

        }

    }



    int max() {

        if(root == null) return -1;

        else return max(root);

    }



    private int max(Node current) {

        if(current.right() == null) return current.value();

        else return max(current.right());

    }



    int min() {

        if(root == null) return -1;

        else return min(root);

    }



    private int min(Node current) {

        if(current.left() == null) return current.value();

        else return min(current.left());

    }



    void ordinal() {

        if (root == null) return;

        else ordinal(root);

    }



    void ordinal(Node current) {

        if(current.left() != null) ordinal(current.left());

        System.out.println(current.value() + " ");

        if(current.right() != null) ordinal(current.right());

    }



    public static void main(String[] args) {

        Tree t = new Tree();

        t.add(50);

        t.add(6);

        t.add(29);

        t.add(100);

        t.add(34);

        t.add(45);

        t.add(4);

        t.add(68);

       

        t.ordinal();

        System.out.println(t.contains(34));

        assert t.contains(34);

        assert t.contains(6);

        assert !t.contains(110);

        assert t.max() == 100;

        assert t.min() == 4;

       

        t.remove(50);

        t.remove(45);

        t.remove(6);

        t.ordinal();

    }

}