【数据结构与算法】二叉排序树Java实现

Java二叉排序树：

    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.List;

    /**
     * 二叉排序树
     * @author wxg
     */
    public  class BST<E>{
        private Node<E> root = null;
        private int size = 0;
        private Comparator<E> compare;
        public BST(Comparator<E> compare){
            this.compare = compare;
        }
        public int size() {
            return size;
        }

        public void create(Object[] objects){
            if(objects==null||objects.length<=0)
                return;
            for(int i=0;i<objects.length;i++){
                add((E) objects[i]);
            }
        }

        public E find(E ele) {
            Node<E> node = root;
            while (node != null) {
                if (node.value == ele)
                    return ele;
                node =  compare.compare(node.value,ele) > 0 ? node.left : node.right;
            }
            return null;
        }

        public void add(E ele) {
            add(ele,true);
        }

        public void add(E ele,boolean isNotRepeat){
            if(ele==null)
                return;
            Node<E> node = new Node<>();
            node.value = ele;
            if(root==null){
                root = node;
            }else {
                if(isNotRepeat){
                    if (find(ele)!=null)
                        return;
                }
                Node<E> troot = root;
                Node<E> tnode = null;
                while (troot!=null){
                    tnode = troot;
                    troot = compare.compare(tnode.value,ele) > 0 ? tnode.left : tnode.right;
                }
                if(compare.compare(tnode.value,ele)>0){
                    tnode.left = node;
                } else{
                    tnode.right = node;
                }
            }
            size++;
        }

        public void remove(E ele) {
            if (root == null)
                new NullPointerException();
            Node<E> parent = root;
            Node<E> current = root;
            boolean isLeftChild = false;
            while (current.value != ele) {
                parent = current;
                if (compare.compare(current.value,ele) > 0) {
                    isLeftChild = true;
                    current = current.left;
                } else {
                    isLeftChild = false;
                    current = current.right;
                }
                if (current == null) {
                    return;
                }
            }
            if (current.left == null && current.right == null) {
                if (current == root) {
                    root = null;
                }
                if (isLeftChild) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            } else if (current.right == null) {
                if (current == root) {
                    root = current.left;
                }
                if (isLeftChild) {
                    parent.left = current.left;
                } else {
                    parent.right = current.right;
                }
            } else if (current.left == null) {
                if (current == root) {
                    root = current.right;
                }
                if (isLeftChild) {
                    parent.left = current.left;
                } else {
                    parent.right = current.right;
                }
            } else {
                Node<E> curr = current.right;
                Node<E> p = curr;
                while (curr.left != null) {
                    p = curr;
                    curr = curr.left;
                }
                if (isLeftChild) {
                    parent.left = curr;
                } else {
                    parent.right = curr;
                }
                curr.left = current.left;
                curr.right = current.right;
                p.left = null;
                p.right = null;
                current = curr;
            }
            size--;
        }

        private static class Node<E>{
            E value;
            Node<E> left;
            Node<E> right;
        }

        public E min(){
            return findMinNode(root).value;
        }

        public E max(){
            return findMaxNode(root).value;
        }

        private Node<E> findMinNode(Node<E> node){
            if(root==null)
                return null;
            if(node.left==null)
                return node;
            else return findMinNode(node.left);
        }

        private Node<E> findMaxNode(Node<E> node){
            if(root==null)
                return null;
            if(node.right==null)
                return node;
            else return findMaxNode(node.right);
        }

        public List<E> getAll(){
            List<E> list = new ArrayList<>(this.size);
            each(root,list);
            return list;
        }
        private void each(Node<E> node,List<E> list){
            if(node!=null){
                list.add(node.value);
                each(node.left,list);
                each(node.right,list);
            }
        }
        public boolean contains(E ele){
            E e = find(ele);
            return e==null?false:true;
        }
    }