java实现TreeSet，迭代器使用二叉查找树，每个节点有前驱和后继

心已赠人 2022-06-09 03:41 152阅读 0赞

代码摘抄自[数据结构][Link 1]与[算法][Link 1]分析（[Java][]语言）的课后题的答案，但是自己把程序理解了一遍。答案不仅有错，而且错还挺多，基本测试好了，应该没有错误了，但是不排除你们把代码拿去实验又发现有错误，如若发现请回复我下(..•˘\_˘•..)

解释一下，此二叉树的节点类，除了有左右孩子链之外，还有**前驱链和后继链**，这个前驱后继就是迭代器的顺序来的，即刚好比当前节点的小的节点，和刚好比当前节点大的节点。

此代码重点在于，处理好插入和删除操作时，前驱和后驱链接的变化，以及对于插入和删除操作情况的分类（从少数情况开始划分到多数情况，比如使用if else的嵌套时，把剩余的大多数情况放到最后一个else里）。

TreeSet实现类：

package four;
    
    import java.util.*;
    
    
    class UnderflowException extends Exception { };
    public class MyTreeSet2<AnyType extends Comparable<? super AnyType>>
    {
    private static class BinaryNode<AnyType>//节点类，静态内部类
    {
    BinaryNode( AnyType theElement )//一个参数的构造器
    { this( theElement, null, null, null, null ); }
    BinaryNode( AnyType theElement,
    BinaryNode<AnyType> lt, BinaryNode<AnyType> rt,
    BinaryNode<AnyType> nt, BinaryNode<AnyType> pv )
    { element = theElement; left = lt; right = rt; next = nt; prev = pv; }
    AnyType element;
    BinaryNode<AnyType> left;
    BinaryNode<AnyType> right;
    BinaryNode<AnyType> next;
    BinaryNode<AnyType> prev;
    }
    public java.util.Iterator<AnyType> iterator()
    {
    return new MyTreeSet2Iterator( );
    }
    private class MyTreeSet2Iterator implements java.util.Iterator<AnyType>
    {
    private BinaryNode<AnyType> current = findMin(root);
    private BinaryNode<AnyType> previous;
    private int expectedModCount = modCount;
    private boolean okToRemove = false;
    private boolean atEnd = false;
    public boolean hasNext()
    { return !atEnd; }
    public AnyType next()
    {
    		if( modCount != expectedModCount )
    		throw new java.util.ConcurrentModificationException( );
    		if( !hasNext( ) )
    		throw new java.util.NoSuchElementException( );
    		AnyType nextItem = current.element;
    		previous = current;
    		current = current.next;
    		if (current == null)//如果向后平移后，current为空则到达最后
    		atEnd = true;
    		okToRemove = true;
    		return nextItem;
    }
    public void remove()
    {
    	if( modCount != expectedModCount )//迭代过程只能删一次
    	throw new java.util.ConcurrentModificationException( );
    	if( !okToRemove )//在某一次迭代过程中，一个元素在删除，就不能再被重复删除了
    	throw new IllegalStateException( );
    	MyTreeSet2.this.remove( previous.element );
    	okToRemove = false;
    }
    }
    public MyTreeSet2()
    { root = null; }
    public void makeEmpty()
    {
    modCount++;
    root = null;
    }
    public boolean isEmpty()
    { return root == null; }
    public boolean contains( AnyType x )
    { return contains( x, root ); }
    public AnyType findMin() throws UnderflowException
    {
    if ( isEmpty() )
    throw new UnderflowException();
    else
    return findMin( root ).element;
    }
    public AnyType findMax() throws UnderflowException
    {
    if ( isEmpty() )
    throw new UnderflowException();
    else
    return findMax( root ).element;
    }
    public void insert( AnyType x )
    { root = insert( x, root, null, null ); }
    public void remove( AnyType x )
    { root = remove( x, root ); }
    public void printTree()
    {
    if ( isEmpty() )
    System.out.println( "Empty tree" );
    else
    printTree( root );
    }
    private void printTree( BinaryNode<AnyType> t )
    {
    if ( t != null )
    {
    printTree( t.left );
    System.out.println( t.element );
    printTree( t.right );
    }
    }
    private boolean contains( AnyType x, BinaryNode<AnyType> t )
    {
    if ( t == null )
    return false;//空树或者此树确实不包含x元素
    int compareResult = x.compareTo( t.element );
    if ( compareResult < 0)
    return contains( x, t.left );
    else if ( compareResult > 0)
    return contains( x, t.right );
    else
    return true; // match
    }
    private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
    {
    if ( t == null )
    return null;//只可能是空树时，才会返回null
    else if ( t.left == null )
    return t;
    return findMin( t.left );
    }
    private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
    {
    if ( t == null )
    return null;//只可能是空树时，才会返回null
    else if ( t.right == null )
    return t;
    return findMax( t.right );
    }
    private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t,
    BinaryNode<AnyType> nt, BinaryNode<AnyType> pv )//按照迭代器的顺序，nt是下一个元素，pv是上一个元素
    {
    		if ( t == null )//空树或者当元素找到最终位置
    		{
    			modCount++;
    			BinaryNode<AnyType> newNode = new BinaryNode<AnyType>( x, null, null, nt, pv);
    			if (nt != null)//如果后继不为空，那么置后继的前驱为新节点
    			{
    			nt.prev = newNode;
    			newNode.next=nt;
    			}
    			if (pv != null)//如果前驱不为空，那么置前驱的后继的新节点
    			{
    			pv.next = newNode;
    			newNode.prev=pv;
    			}
    			return newNode;
    		}
    		int compareResult = x.compareTo( t.element );//以下两个if执行的insert函数的后两个参数是用来更新前驱和后继的
    		if ( compareResult < 0)
    		t.left = insert( x, t.left, t, pv );//如果往左走，那么t.left是当前节点，而t是后继节点。而上一次传的前驱就是此当前节点的前驱
    	                                     //之所以这么说，因为往左走，肯定后继需要更新，因为现在的后继是更接近x的后驱
    	                                    //而x的前驱无法确定，但用上一次传的前驱肯定是当前最接近x的前驱
    	                                   //有一种情况，如果一直往左，那么传的前驱一直都是空，因为这个x是最小的元素，不会有前驱
    		else if ( compareResult > 0)//往右走，同理
    		{
    		t.right = insert( x, t.right, nt, t );
    		}
    		else
    		; // duplicate
    		return t;
    }
    private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
    {
    		if ( t == null )//如果为空树或者没有找到x元素
    		return t; // not found
    		int compareResult = x.compareTo( t.element );
    		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 ) //有两个孩子，继续递归函数
    		{//只需要改变t的值，前驱后继链不需要改，因为是对的
    		t.element = findMin( t.right ).element;
    		t.right = remove( t.element, t.right );
    		}
    		//在递归终点中，注意只需把前驱后继的变化做对，而孩子链的改变则交给return和上一层递归函数即可
    		
    		else if(t.left == null && t.right == null )//删除节点为叶子节点
    		{
    			modCount++;
    			
    			if(t.prev == null&&t.next == null)//这是一个特殊情况，当树只有根节点时
    				//因为进入了这层if，所以t没有孩子，因为前驱后继为空，所以该树为只有根节点的树
    				//因为只有根，删除根后，树为空，需要返回null到public的remove函数中，置root为null
    			{
    				return null;
    			}
    			//因为是叶子节点，要么前驱是父节点，要么后继是父节点,进一步分析，三种情况
    			//如果叶子节点从根一直往左的，前驱为null
    			//如果叶子节点从根一直往右的，后继为null
    			//剩下的就是大多数情况，和根形成了Z字形，即该叶子节点前驱后继都不为空
    			if(t.prev==null)//如果t是其父节点的左孩子,t的后继是t的父节点
    			{
    				t.next.prev=null;
    				//t.next.left=null;
    				return null;
    			}
    			else if(t.next==null)
    			{
    				t.prev.next=null;
    				//t.prev.right=null;
    				return null;
    			}//剩下这两种情况是t既有前驱也有后继，不可能再报空指针异常
    			//因为是z字形，所以当前t肯定有前驱和后继，不用判断前驱后继是否为空
    			else if(t.next.left==t)
    			{
    				
    				t.next.prev=t.prev;
    				t.prev.next=t.next;
    				return null;
    			}
    			else if(t.prev.right==t)
    			{
    				
    				t.prev.next=t.next;
    				t.prev.next=t.next;
    				return null;
    			}
    			
    		}
    		else//删除节点为单孩子节点，因为有孩子，所以前驱后继至少有一个不为空
    		{
    		modCount++;//以下有三种情况
    		if(t==root)//如果该单孩子节点为根节点，向左或向右，即现在树只有二个节点
    		{
    			if(t.next==null)
    			{
    				BinaryNode<AnyType> newroot=t.prev;
    			    newroot.next=null;
    //			    if(findMin(newroot.right)!=null)
    //			       findMin(newroot.right).next=null;
    			    return newroot;
    			}
    			else if(t.left==null)
    			{
    				BinaryNode<AnyType> newroot=t.next;
    			    newroot.prev=null;
    //			    if(findMax(newroot.left)!=null)
    //			    	findMax(newroot.left).prev=null;
    			    return newroot;
    			}
    		}
    		else if(t.prev==null&&t.next!=null)//前驱为空是Z字形，且向左凸出，从根节点一直往左到了t才往右
    		{
    			t.next.next.prev=t.next;
    			t.next.next=t.next.next;
    			t.next.prev=null;//t的后继的前驱必须置空，因为t已经被删除了
    			return t.next;
    		}
    		else if(t.next==null&&t.prev!=null)//后继为空是Z字形，且向右凸出，从根节点一直往右到了t才往左
    		{
    			t.prev.prev.next=t.prev;
    			t.prev.prev=t.prev.prev;
    			t.prev.next=null;//t的前驱的后驱必须置空，因为t已经被删除了
    			return t.prev;
    		}
    		//剩下的就是大多数情况了，t既有前驱也有后继，那就把前驱后继相连
    		t.prev.next = t.next; // update next and prev links
    		t.next.prev = t.prev;
    		t = ( t.left != null ) ? t.left : t.right;//把t的引用变为t的唯一孩子引用，在返回上一层递归时，会把新t置为某节点的孩子节点
    		}
    		return t;
    }
    private BinaryNode<AnyType> root;
    int modCount = 0;
    }

测试类，我测试的情况可能不够多，不够复杂。大家也可以尝试下：

package four;
    
    import java.util.TreeSet;
    
    public class MyTreeSet2Test {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    		
            MyTreeSet2<Integer> test2=new MyTreeSet2<Integer>();
    	    
    		test2.insert(10);
    		test2.insert(15);
    		test2.insert(12);
    		test2.insert(17);
    		test2.insert(7);
    		test2.insert(8);
    		test2.insert(2);
    		
    		test2.remove(7);
    		//test2.remove(7);
    		//test2.remove(12);
    		test2.remove(15);
    //		System.out.println(test2.contains(4));
    		test2.printTree();
    		System.out.println();
    		java.util.Iterator<Integer> it=test2.iterator();
    		
    		while(it.hasNext())
    
    		{
    
    		   System.out.println(it.next());
    
    		     
    		      //it.remove();
    		}
    
    	}
    
    }

[Link 1]: http://lib.csdn.net/base/datastructure
[Java]: http://lib.csdn.net/base/java