package practice;public class TestMain {    public static void main(String[] args) {        int[] ao = {50,18,97,63,56,3,71,85,54,34,9,62,45,94,66,65,7,19,22,86};        Integer[] a = new Integer[20];        for (int i = 0; i < a.length; i++) {            a[i] = new Integer(ao[i]);        }        BinarySortTree
     
       tree = new BinarySortTree
      
       ();        for (int i = 0; i < a.length; i++) {            tree.put(a[i], a[i].toString());        }        /*tree.delete(3);        System.out.println("min = "+tree.min()+" max = "+tree.max());        tree.delete(97);        System.out.println("min = "+tree.min()+" max = "+tree.max());        tree.delete(19);        tree.delete(18);        tree.delete(85);        System.out.println();        tree.delete(99);*/            }}/* * 二叉查找树及其操作的递归实现 * 二叉查找树：左节点比根节点小，左节点比根节点大。 */class BinarySortTree
       
        , V>{        Node root;    /*     * Node结点类     */    class Node{        private Node left, right; //左右子树        private K key;        private V value;         private int N; //节点所在树的子节点数（包括自己）                private Node(K key, V value) {            this.key = key;            this.value = value;            this.N = 1;        }                        public K getKey() {            return key;        }    }    /*     * 插入新节点     * O(lgn)     */    public void put(K key, V value) {        root = put(key, value, root);    }        private Node put(K key, V value, Node node) {        if (node == null) { return new Node(key, value);}                if (compare(key, node.key) == 0)     { node.value = value;} //如果key相等则更新值        else if (compare(key, node.key) < 0) { node.left = put(key, value, node.left);} //进入左子树        else if (compare(key, node.key) > 0) { node.right = put(key, value, node.right);} //进入右子树        node.N = size(node.left) + size(node.right) + 1; //子节点数                return node;    }    /*     * 查找     */    public V get(K key) {        return get(key, root);    }        private V get(K key, Node node) {        if (node == null) { return null;}                if (compare(key, node.key) < 0)      { return get(key, node.left);}        else if (compare(key, node.key) > 0) { return get(key, node.right);}        else                                 { return node.value;} //递归结束条件，找到key    }    /*     * 获取最大最小值     */    public K min() {        return min(root).key;    }        private Node min(Node node) {        if (node.left == null) { return node;}        else                   { return min(node.left);}    }        public K max() {        return max(root).key;    }        private Node max(Node node) {        if (node.right == null) { return node;}        else                    { return max(node.right);}    }    /*     * 获取键的排名     */    public int rank(K key) {        return rank(key, root);    }        private int rank(K key, Node node) {        if (node == null) { return 0;} //键不存在返回0                if (compare(key, node.key) < 0)      { return rank(key, node.left);}        else if (compare(key, node.key) > 0) { return size(node.left) + 1 + rank(key, node.right);}                                             //当查找进入右子树时，加上同级左子树的大小，再加1（父节点本身）        else                                 { return size(node.left);} //该节点左子树的大小（它的左子树的key全部比它小）    }    /*     * 根据排名获取键     */    public Node select(int N) {        return select(N, root);    }        private Node select(int N, Node node) {                int t = size(node.left) + 1; //获取当前节点在以它为根节点的树中的排名（从1开始排）        if (N < t)      { return select(N, node.left);} //与当前排名比较，选择进入左子树还是右子树        else if (N > t) { return select(N - t, node.right);}         //进入右子树时，右子树所有的节点的排名都要加上"同级左子树的大小，再加1（父节点本身）"，所以 N - t        else            { return node;}    }    /*     * 删除最小键     */    public void deleteMin() {        root = deleteMin(root);    }    private Node deleteMin(Node node) {        if (node.left == null) { return node.right;} //将最小节点的右子树连在他的父节点上即将它删除        node.left = deleteMin(node.left);         node.N = size(node.left) + size(node.right) + 1; //更新树的大小        return node;    }    /*     * 删除指定键     */    public void delete(K key) {        root = delete(key, root);    }    private Node delete(K key, Node node) {        if (node == null) { return null;} //找不到键，不做任何处理，原样返回                if (compare(key, node.key) < 0)      { node.left = delete(key, node.left);} //向左向右找        else if (compare(key, node.key) > 0) { node.right = delete(key, node.right);}        else {            if (node.right == null) { return node.left;} //如果要删的节点有一边时null，直接把另一条子树连到父节点上            if (node.left== null)   { return node.right;}             /*Node tnode = min(node.right);            node.right = deleteMin(node.right);            tnode.left = node.left;            tnode.right = node.right;            tnode.N = size(tnode.left) + size(tnode.right) + 1;            return tnode;*/            //上下两段代码实现了同样的功能，充分体现了差距            Node tnode = node;  //将右子树中的最小值（后继节点）连到父节点上，或左子树中的最大值（前趋节点）也可以            node = min(tnode.right);            node.right = deleteMin(tnode.right); //把将要连到父节点上的那个后继节点在当前位置删除            node.left = tnode.left; //更新左右子树        }                node.N = size(node.left) + size(node.right) + 1; //更新树的大小        return node;    }    /*     * key1 <  key2 -1     * key1 >  key2  1     * key1 == key2  0     */    private int compare(K key1, K key2) {        return key1.compareTo(key2);     }        private int size(Node node) {        if (node == null) { return 0;}        else              { return node.N;}    }        /*     * 中序遍历     */    public void print(Node node) {        if (node == null) {            return;        }        print(node.left);        System.out.print(node.key+" ");        print(node.right);    }}
       
      
     

算法动态演示

http://www.cs.usfca.edu/~galles/visualization/BST.html