实现Treeset-白红宇

TreeSet实际上就是用二叉树实现的；代码如下：

public class MyTreeSet
    
     > {    private BinaryNode
     
       root; //root    int modCount = 0 ;//modifiy time    public MyTreeSet(){        root = null;    }    private class BinaryNode
      
       {        T data;        BinaryNode
       
         left;        BinaryNode
        
          right;        BinaryNode
         
           parent; public BinaryNode(T data) { this.data = data; } public BinaryNode(T data, BinaryNode
          
            left, BinaryNode
           
             right, BinaryNode
            
              parent) { this.data = data; this.left = left; this.right = right; this.parent = parent; } } public Iterator
             
               iterator(){ return new MyTreeSetIterator(); } private class MyTreeSetIterator implements Iterator
              
               { private BinaryNode
               
                 current = findMin(root); private BinaryNode
                
                  previous; private int expectedModCount = modCount; private boolean okToRemove = false; private boolean atEnd = false; @Override public boolean hasNext() { return !atEnd; } @Override public T next() { if (modCount != expectedModCount){ throw new ConcurrentModificationException(); } if(!hasNext()){ throw new NoSuchElementException(); } T nextItem = current.data; previous = current; //按照顺序排列的话，是从小到大排序，所以下一个数据肯定要比当前的大，所以在右边 // if there is a right child , next node is min in right subtree if (current.right != null){ current = findMin(current.right); }else { // 否则就找父亲，并且该节点是父亲的左孩子，那么下一个数据就是他的父亲，因为他的父亲比他大 BinaryNode
                 
                   child = current; current = current.parent; //if current do have parent while(current != null && current.left != child){ //这句话的作用是当到达最右边时，向上遍历，一直到达根，一直到current = null时退出 child = current; current = current.parent; } if (current == null){ //已经到了最右边， atEnd = true ; } } okToRemove = true; return nextItem; } @Override public void remove() { if (modCount != expectedModCount){ throw new ConcurrentModificationException(); } if (!okToRemove){ throw new IllegalStateException(); } MyTreeSet.this.remove(previous.data); okToRemove= false; // only one element will be deleted every next } } public void makeEmpty(){ modCount ++; root = null; } public boolean isEmpty(){ return root == null; } public boolean contains(T x){ return contains(x,root); } public T findMin() throws BufferUnderflowException{ if (isEmpty()){ throw new BufferUnderflowException(); } else return findMin(root).data; } public T findMax() throws BufferUnderflowException{ if (isEmpty()){ throw new BufferUnderflowException(); } else return findMax(root).data; } public void insert(T x){ root = insert(x,root,null); } public void remove(T x){ root = remove(x,root); } public void printTree(){ if (isEmpty()){ System.out.println("Empty Tree"); }else { printTree(root); } } private void printTree(BinaryNode
                  
                    t){ if (t != null){ printTree(t.left); System.out.println(t.data); printTree(t.right); } } private boolean contains(T x,BinaryNode
                   
                     t){ if (t == null) return false; int compareResult = x.compareTo(t.data); if (compareResult < 0){ return contains(x,t.left); }else if (compareResult > 0){ return contains(x,t.right); }else return true; } private BinaryNode
                    
                      findMin(BinaryNode
                     
                       t){ if (t == null){ return null; } else if (t.left == null){ return t; } return findMin(t.left); } private BinaryNode
                      
                        findMax(BinaryNode
                       
                         t){ if (t == null) return null; else if (t.right == null) return t; else return findMin(t.right); } private BinaryNode
                        
                          insert(T x, BinaryNode
                         
                           t, BinaryNode
                          
                            pt){ if (t == null){ modCount ++ ; return new BinaryNode
                           
                            (x,null,null,pt); } int comapreResult = x.compareTo(t.data); if (comapreResult < 0 ){ t.left = insert(x,t.left,t); }else if (comapreResult > 0){ t.right = insert(x,t.right,t); }else ; //duplicate return t; } private BinaryNode
                            
                              remove(T x,BinaryNode
                             
                               t){ if (t == null){ return t; } int compareResult = x.compareTo(t.data); if (compareResult < 0){ t.left = remove(x,t.left); }else if(compareResult > 0){ t.right = remove(x,t.right); }else if (t.left != null && t.right != null){ // it has two children t.data = findMin(t.right).data; // give the smallest data in right to this node t.right = remove(t.data,t.right) ; //remove the smallest in right tree }else if (t.left == null && t.right == null){ // remove the parent's relation with this node modCount ++ ; BinaryNode
                              
                                pt = t.parent; if (pt == null){ // if this tree only has one node return null; } int result = t.data.compareTo(pt.data); if (result < 0 ){ pt.left = null; }else { pt.right = null; } }else { // has only left or right child modCount ++; BinaryNode
                               
                                 oneChild; oneChild = t.left != null ? t.left : t.right; oneChild.parent = t.parent; t = oneChild; } return t; }}复制代码

测试：

public class MyTreeSetTest {    public static void main(String[] args)  {        MyTreeSet
    
      test1 = new MyTreeSet<>();        test1.insert(3);        test1.insert(4);        test1.insert(5);        test1.insert(6);        test1.insert(7);        test1.insert(8);        test1.insert(9);        java.util.Iterator
     
       it=test1.iterator();        while(it.hasNext())        {            System.out.println(it.next());        }    }}复制代码