java实现TreeSet，迭代器使用二叉查找树，每个节点有父节点链

迈不过友情╰ 2022-06-09 02:08 142阅读 0赞

代码摘抄自数据结构与算法分析（java语言）的课后题的答案，但是自己把程序理解了一遍，其实答案也有错误，比如原答案无法删除叶子节点，因为写答案的人没有去实现这个功能。

注释已经把程序解释得很清楚了。

下面放代码，先是TreeSet实现类：

package four;
    
    import java.util.*;
    class UnderflowException extends Exception { };
    public class MyTreeSet<AnyType extends Comparable<? super AnyType>>
    {
    private static class BinaryNode<AnyType>//节点类，静态内部类
    {
    	BinaryNode( AnyType theElement )
    	{ this( theElement, null, null, null ); }
    	BinaryNode( AnyType theElement,
    	BinaryNode<AnyType> lt, BinaryNode<AnyType> rt,
    	BinaryNode<AnyType> pt )
    	{ element = theElement; left = lt; right = rt; parent = pt; }
    	AnyType element;
    	BinaryNode<AnyType> left;
    	BinaryNode<AnyType> right;
    	BinaryNode<AnyType> parent;
    }
    public java.util.Iterator<AnyType> iterator()//方法返回一个迭代器
    {
    return new MyTreeSetIterator( );
    }
    private class MyTreeSetIterator 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; }//只要没到最后就有next
    
    		public AnyType next()
    		{
    		if( modCount != expectedModCount )//如果迭代过程中被修改，报异常
    		throw new java.util.ConcurrentModificationException( );
    		if( !hasNext( ) )//如果没有next也就是到了最后，报异常
    		throw new java.util.NoSuchElementException( );
    		AnyType nextItem = current.element;//把current的元素当成下一个元素
    		previous = current;//把当前指针变成之前指针
    		// if there is a right child, next node is min in right subtree，右子树的最左孩子就是刚好比当前节点大的那个点
    		if (current.right != null)
    		{
    		current = findMin(current.right);
    		}
    		else
    		{
    		// else, find ancestor that it is left of，否则就找父亲，且该节点是父节点的左孩子
    		BinaryNode<AnyType> child = current;
    		current = current.parent;
    		while ( current != null && current.left != child)//可以找到一个祖先，且最初的current节点在这个祖先的左子树
    		{
    		child = current;
    		current = current.parent;
    		}
    		if (current == null)//这里很有可能是，在到了最右点，一直执行上面循环到了根节点，然后根节点没有父节点，设置为true
    		atEnd = true;
    		}
    		okToRemove = true;
    		return nextItem;
    		}
    
    		public void remove()
    		{
    		if( modCount != expectedModCount )
    		throw new java.util.ConcurrentModificationException( );
    		if( !okToRemove )
    		throw new IllegalStateException( );
    		MyTreeSet.this.remove( previous.element );//想象迭代器有个指针是在previous和current中间的，当要删除时，这两个点只有previous点的值被返回了，current点的值还没有被返回
    		okToRemove = false;//每经过一个点即next函数后，okToRemove就会置为真，删了就置为假
    		//也就是说，每次迭代过程，刚经过的点有且仅有一次被删除，因为删完okToRemove就置为假了
    		}
    }
    public MyTreeSet()//
    { root = null; }
    public void makeEmpty()
    {
    modCount++;//清空也算一次操作，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 ); }//这个地方不能写成insert( x, root, null )，因为在空树插入根节点时
                             //如果是上述写法，那么insert返回了根节点的引用，但是二叉树成员变量root还是空，并没有进行更新
                             //实际上在有了根节点以后，这个函数就是一直在把同一个引用赋值给同一个引用
    public void remove( AnyType x )
    {  root = remove( x, root ); }//这个地方就可以去掉root = ，因为删除时如果根为空就直接返回空，但不为空时
                       //根的引用就一定不是null，不像insert函数需要把空的树更新为只有根节点的一个树
                       //但思考后感觉不去掉好，因为就不用在私有remove函数里手动把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;
    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;
    else if ( t.left == null )
    return t;
    return findMin( t.left );
    }
    private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
    {
    if ( t == null )
    return null;
    else if ( t.right == null )
    return t;
    return findMax( t.right );
    }
    private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t,
    BinaryNode<AnyType> pt )
    {
    		if ( t == null )
    		{
    		modCount++;
    		return new BinaryNode<AnyType>( x, null, null, pt);//递归的终点，最终返回一个点，左右孩子为空，有父节点
    		}
    		int compareResult = x.compareTo( t.element );
    		if ( compareResult < 0)
    		t.left = insert( x, t.left, t );//在过程中，一直把t的左孩子赋值给t的左孩子，第三个参数只是为了到达终点时在构造节点知道哪个是父节点
    		else if ( compareResult > 0)
    		t.right = insert( x, t.right, t );
    		else
    			; // duplicate
    		return t;//递归的过程中每次调用的返回，返回第二个参数，最外层返回的是根节点
    }
    private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
    {
    if ( t == null )
    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 ) // two children，找到点但有两个孩子
    {
    t.element = findMin( t.right ).element;//找到右子树的最小元素
    t.right = remove( t.element, t.right );//从右子树根节点删除上述最小元素
    }
    else if(t.left == null&&t.right == null)//找到点，没有孩子
    {
    	//递归的第一个终点，因为在递归的过程中一直有一个赋值的过程，本来到了递归的终点只需要把需要改变的引用改变了就行
    	//但是，递归的终点就相当于是特殊的过程，所以必须返回一个正确的值，看终点的上一层递归，是把t的左孩子赋值给t的左孩子
    	//而这里删掉的是没有孩子的节点，所以返回null值给父节点
    	modCount++;
    	BinaryNode<AnyType> pt=t.parent;
    	if(pt==null)//这是一个特殊情况，当树只有根节点时，pt为空，所以执行pt.element会报空指针异常
    		//因为进入了这层循环，所以t没有孩子，因为pt为空，所以t也没有父亲，所以该树为只有根节点的树
    		//因为只有根，删除根后，树为空，需要返回null到public的remove函数中，置root为null
    	{
    		return null;
    	}
    	int result=t.element.compareTo(pt.element);
    	if(result<0)
    		pt.left=null;
    	else
    		pt.right=null;
    	return null;
    }
    else//找到点，只有一个孩子，左或者右
    {
    	//这里是另一个递归终点，递归的终点就相当于是特殊的过程，所以必须返回一个正确的值
    	//看上一层递归过程，是把被删节点的父节点的左孩子赋值给被删节点的父节点的左孩子
    	//因为是终点，所以要把被删节点的唯一孩子赋值给被删节点的父节点的左孩子
    	modCount++;
    	BinaryNode<AnyType> oneChild;
    	oneChild = ( t.left != null ) ? t.left : t.right;//
    	oneChild.parent = t.parent; // update parent link，相当于孙子直接变成了儿子
    	t = oneChild;
    }
    return t;
    }
    private BinaryNode<AnyType> root;
    int modCount = 0;
    }

然后是测试类：

package four; import java.util.TreeSet; public class MyTreeSetTest { public static void main(String[] args) { // TODO Auto-generated method stub MyTreeSet<Integer> test1=new MyTreeSet<Integer>(); test1.insert(10); test1.insert(6); test1.insert(4); //test1.remove(4); //TreeSet set=new TreeSet(); // System.out.println(test1.contains(4)); // test1.printTree(); java.util.Iterator<Integer> it=test1.iterator(); while(it.hasNext()) { System.out.println(it.next()); it.remove(); it.remove(); } } }