binarytreeuos.java

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

		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> 
		@param x item to be inserted as the left parent */
	public void insertParentLeftGo(Object x) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist to do insertParentLeftGo.");
		
		if (cur==rootNode)
		{	
			insertRootLeft(x);
			goRoot();
		}
		else
		{
			BinaryNodeUos temp = createNewNode(x);
			if (parent.leftNode()==cur)
				parent.setLeftNode(temp);
			else
				parent.setRightNode(temp);
			temp.setRightNode(cur);
			cur = temp;
		}
	}

	/**	Insert x above and right of current item and make x current item. <br> 
		Analysis: Time = O(1) <br> 	
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul>
		@param x item to be inserted as the right parent */
	public void insertParentRightGo(Object x) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist to do insertParentRightGo.");   
		
		if (cur==rootNode)
		{
			insertRootRight(x);
			goRoot();
		}
		else
		{	    
			BinaryNodeUos temp = createNewNode(x);
			if (parent.leftNode()==cur)
				parent.setLeftNode(temp);
			else
				parent.setRightNode(temp);
			temp.setLeftNode(cur);
			cur = temp;
		}
	}

	/**	Set the left subtree of the root to t and goRoot(). <br> 	
		Analysis: Time = O(1) <br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> 
		@param t tree to be inserted at the root */
	public void setRootLeftSubtree(LinkedSimpleTreeUos t) throws ContainerEmptyUosException 
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set the root's subtree if there is not root");

		super.setRootLeftSubtree(t);
		goRoot();
	}

	/**	Set the right subtree of the root to t and goRoot. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> 
		@param t tree to be inserted at the root */
	public void setRootRightSubtree(LinkedSimpleTreeUos t) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set the root's subtree if there is not root");

		super.setRootRightSubtree(t);
		goRoot();
	}

	/**	Set the left subtree of the current position to t. <br>
		Analysis: O(1) <br> 
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> 
		@param t tree to be inserted as the left subtree */
	public void setLeftSubtree(BinaryTreeUos t) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist to set a left subtree.");
		
		if (t!=null && !t.isEmpty())
			cur.setLeftNode(t.rootNode);
		else
			cur.setLeftNode(null);
	}

	/**	Set the right subtree of the current position to t. <br> 
		Analysis: O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> 
		@param t tree to be inserted as the right subtree */
	public void setRightSubtree(BinaryTreeUos t) throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist to set a right subtree."); 
		
		if (t!=null && !t.isEmpty())
			cur.setRightNode(t.rootNode);
		else
			cur.setRightNode(null);
	}

	/**	Delete the current item, keeping the nonEmpty subtree
		or if both non-empty, call findReplacementItemPosition. 
		Note that the routine affects only the binary cursor 
		(used in search, etc), not the linear cursor (goForth, etc).<br> 
		Analysis: Time = O(1), when has empty subtree <br>
				<ul><ul>O(n), where n = number items in tree (worst case) </ul></ul><br>
		PRECONDITION: <br>
		<ul>
			itemExists()
			
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("A current item must exist to perform deletion.");
		
		deleteItemAt((LinkedBinaryIteratorUos)currentPosition());
	}

	/**	Delete item x, keeping the non-empty subtree
		or if both non-empty, call findReplacementItemPosition and go to position. <br> 
		Analysis: Time = O(1), when has empty subtree <br>
				O(n), where n = path length to successor <br>
		PRECONDITION: <br>
		<ul>
			has(x)
		</ul> 
		@param x item to be deleted from the tree */
	public void delete(Object x) throws ItemNotFoundUosException
	{
		if (!has(x))	
			throw new ItemNotFoundUosException("Cannot delete since x does not exist in the tree.");
		
		LinkedBinaryIteratorUos savePos, deletePos;      
		savePos = (LinkedBinaryIteratorUos)currentPosition();
		search(x);
		deletePos = (LinkedBinaryIteratorUos)currentPosition();
		goPosition(savePos);
		deleteItemAt(deletePos);
	}

	/**	Is the current position after the bottom of the tree?. <br> 
		Analysis: Time = O(1) */
	public boolean below()
	{
 		return ((cur==null) && (parent!=null || isEmpty()));
	}

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

	/**	Is the current position above the root of the tree?. <br> 
		Analysis: Time = O(1) */
	public boolean above()
	{
		return (parent==null) && (cur==null);
	}

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

	/**	Move prior to the root item of the tree. <br> 
		Analysis: Time = O(1) */
	public void goAbove()
	{
		parent = null;
		cur = null;
	}

	/**	Stack used for linear iterator implementation. */
	protected LinkedStackUos theStack;
  
  	/**	Go to the inorder first item in an inorder traversal of the tree. <br> 
		Analysis: Time = O(n), where n = length of leftmost path in tree */
	public void goFirst()
	{
		theStack = new LinkedStackUos();
		if (rootNode==null)
			goAfter();
		else
		{
			linCur = rootNode;
			while (linCur.leftNode()!=null)
			{
				theStack.insert(linCur);
				linCur = linCur.leftNode();
			}
		}
	}

	/**	Advance to the next inorder item in the tree. <br> 
		Analysis: Time = O(n), where n = length of the leftmost path in a subtree <br>
		PRECONDITION: <br>
		<ul>
			!after()
		</ul>
		*/  
	public void goForth() throws AfterTheEndUosException
	{
		if (after())
			throw new AfterTheEndUosException("Cannot advance in the tree since already after.");
		
		if (theStack==null)
			goFirst();
		else if (linCur.rightNode()!=null)
		{
			linCur = linCur.rightNode();
			while (linCur.leftNode()!=null)
			{
				theStack.insert(linCur);
				linCur = linCur.leftNode();
			}
		}
		else
		{
			if (theStack.isEmpty())
				linCur = null;	
			else
			{
				linCur = (BinaryNodeUos)theStack.item();
				theStack.deleteItem();
			}
		}
	}

	/**	Move to prior to the first item. <br> 
		Analysis: Time = O(1) */
	public void goBefore()
	{
		theStack = null;
		linCur = null;
	}

	/**	Move to after the last item. <br> 
		Analysis: Time = O(l), where l = length of rightmost path in tree */
	public void goAfter()
	{
		linCur = rootNode;
		while (linCur!=null)
			linCur = linCur.rightNode();
		if (theStack==null)
			theStack = new LinkedStackUos();
		else
			theStack.wipeOut();
	}

	/**	Move to the root item of the tree. <br> 
		Analyis: Time = O(1) */
	public void goRoot()
	{
		parent = null;
		cur = rootNode();
	}


	/**	Advance to the root of the leftSubtree. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!below()
		</ul> */
	public void goLeft() throws AfterTheEndUosException
	{
		if (below())
			throw new AfterTheEndUosException("Cannot advance to the left since already below.");
			
		if (above())
			goRoot();
		else
		{
			parent = cur;
			cur = cur.leftNode();
		}
	}

	/**	Advance to the root of the rightSubtree. <br> 
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!below()
		</ul> */
	public void goRight() throws AfterTheEndUosException
	{
		if (below())
			throw new AfterTheEndUosException("Cannot advance to the right since already below.");
	
		if (above())
			goRoot();
		else
		{
			parent = cur;
			cur = cur.rightNode();
		}
	}

	/**	Return the number of times x occurs. <br> 
		Analysis: Time = O(n), n = number of items in the data structure 
		@param x item to find how often it occurs in the tree */
	public int frequency(Object x)
	{
		if (isEmpty())
			return 0;
		else
		{
			int result;
			if(membershipEquals(x, rootItem()))
					result = 1;
			else
				result = 0;
			return result + ((BinaryTreeUos)rootLeftSubtree()).frequency(x)
				+ ((BinaryTreeUos)rootRightSubtree()).frequency(x);
		}          
	}
  
	/**	Delete the item in pos and update current position. <br> 
		Analysis: Time = O(1), when it has an empty subtree <br>
				<ul><ul>O(n), where n = path length to successor</ul></ul><br> 
		@param pos iterator position of item to be deleted */
	protected void deleteItemAt(LinkedBinaryIteratorUos pos) 
	{
		BinaryNodeUos delCur, delParent, replaceNode = null;
		boolean foundReplacement;
	  
		delParent = pos.parent;   
		delCur = pos.cur;
		/* Test if there is only one subtree so it can replace the tree */
		if (delCur.rightNode()==null)
		{
			replaceNode = delCur.leftNode();
			foundReplacement = true;
		}
		else if (delCur.leftNode()==null)
		{
			replaceNode = delCur.rightNode();
			foundReplacement = true;
		}
		else
			foundReplacement = false;
	  	  	
		if (foundReplacement)
		{
		/* Set delParent node to refer to the replacement subtree */
			if (delParent==null)
				setRootNode(replaceNode);
			else if (delParent.leftNode()==delCur)
				delParent.setLeftNode(replaceNode);
			else
	 			delParent.setRightNode(replaceNode);
	
			if (parent==delCur)
				parent = delParent;
			else if (cur==delCur)
				cur = replaceNode;
		}
		else
		{
			LinkedBinaryIteratorUos replacePos = findReplacementItemPosition(pos);
			delCur.setItem(replacePos.cur.item());
			deleteItemAt(replacePos);
		}
	}
  
	/**	Create a cloned version of the tree. <br> 
		Analysis: Time = O(n), where n = number of items in the tree */
	public BasicBinaryTreeUos treeClone()
	{
		BinaryTreeUos result = (BinaryTreeUos)super.treeClone();
		result.searchesContinue = searchesContinue;	
		result.objectReferenceComparison = objectReferenceComparison;
		return result;	
	}

	/**	Remove all items from the data structure. <br> 
		Analysis: Time = O(1) */
	public void wipeOut()
	{	
		super.wipeOut();
		goAbove();
		goBefore();
	}	
}