orderediteratedsimpletree.java

国外的数据结构与算法分析用书

import dslib.dispenser.LinkedStackUos;
import dslib.base.LinearIteratorUos;
import dslib.tree.*;

public class OrderedIteratedSimpleTree extends OrderedSimpleTreeUos implements LinearIteratorUos
{
	/**	A stack used for iteration. */
	private LinkedStackUos theStack;

	/**	An empty constructor for the class.
		Analysis: Time = O(1) */
	public OrderedIteratedSimpleTree()
	{
		super();
	}
	
	/**	Second constructor for this class.
		Anlysis: Time = O(1) */
	public OrderedIteratedSimpleTree(OrderedIteratedSimpleTree lt, Object r, OrderedIteratedSimpleTree rt)
	{
		super(lt, r, rt);
	}

	/**	Is the current position before the first item? 
		Analysis : Time = O(1) */
	public boolean before()
	{
		return (cur == null) && (theStack == null);
	}

	/**	Is the current position after the last item? 
		Analysis : Time = O(1) */
	public boolean after()
	{
		return (cur == null) && (theStack != null && theStack.isEmpty());
	}

	/**	Set the current position to be before the first item. 
		Analysis : Time = O(1) */
	public void goBefore()
	{
		cur = null;
		theStack = null;
	}

	/**	Set the current position to be after the last item. 
		Analysis : Time = O(1) */
	public void goAfter()
	{
		cur = null;
		if (theStack == null)
			theStack = new LinkedStackUos();
		else
			theStack.wipeOut();
	}

	/**	Go to the first item in the inorder traversal of the tree.
		Analysis : Time = O(m), where m = length of the leftmost path in tree */
	public void goFirst()
	{
		theStack = new LinkedStackUos();
		if (rootNode == null)
			cur = null;
		else
		{
			cur = rootNode;
			while (cur.leftNode() != null)
			{
				theStack.insert(cur);
				cur = cur.leftNode();
			}
		}
	}

	/**	Advance to the next inorder item in the tree.
		Analysis : Time = O(m), where m = length of the leftmost path in
		cur's right subtree  */
	public void goForth()
	{
		if ((cur == null) && (theStack == null))
			goFirst();
		else if (cur.rightNode() != null)
		{
			cur = cur.rightNode();
			while (cur.leftNode() != null)
			{
				theStack.insert(cur);
				cur = cur.leftNode();
			}
		}
		else
		{
			if (theStack.isEmpty())
				cur = null;
			else
			{
				cur = (BinaryNodeUos)theStack.item();
				theStack.deleteItem();
			}
		}
	}
}