basicbinarytreeuos.java

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

/* BasicBinaryTreeUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */

package dslib.tree;

import dslib.exception.*;

/**	LinkedSimpleTreeUos class with added routines to insert a root 
	item and to delete the root item.  Features from 
	LinkedSimpleTree include access to and setting of the root 
	item and the left and right subtrees. */
public class BasicBinaryTreeUos extends LinkedSimpleTreeUos
{  
  	/**	Construct an empty tree. <br>
		Analysis: Time = O(1) */
	public BasicBinaryTreeUos()
	{
		super();
	}

        /**	Constructor:  make lt, r, and rt the left subtree, root item and right subtree,
		respectively (lt and/or rt can be null for an empty subtree). <br>
		Analysis: Time = O(1) <br>
		@param lt tree to initialize as the left subtree
		@param r item to initialize as the root
		@param rt tree to initialize as the right subtree */
	public BasicBinaryTreeUos(LinkedSimpleTreeUos lt, Object r, LinkedSimpleTreeUos rt)
	{
		super(lt, r, rt);
	}

	/**	Insert x as new root item up to the left of the old root. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted as the new root */
	public void insertRootLeft(Object x) 
	{
		BinaryNodeUos temp = createNewNode(x);
		temp.setRightNode(rootNode);
		rootNode = temp;
	}
  
	/**	Inserts x as new root item up to the right of old root. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted as the new root */
	public void insertRootRight(Object x) 
	{
		BinaryNodeUos temp = createNewNode(x);
		temp.setLeftNode(rootNode);
		rootNode = temp;
	}
  
	/**	Inserts x as new root item up to the right of old root. <br>
		Analysis: Time = O(1) 
		@param x item to be inserted as the new root */
	public void insertRoot(Object x)
	{
		insertRootRight(x);
	}

	/**	Iterator for the tree initialized to the root item. <br>
		Analysis: Time = O(1) */
	public LinkedBinaryIteratorUos newIterator()
	{
		return new LinkedBinaryIteratorUos(this);
	}

	/**	Delete the root of the tree keeping the non-empty subtree,
		or if both non-empty, replace the root item by the item
		specified by findReplacementItemPosition. <br>
		Analysis: Time = O(1) when it has an empty subtree. <br>
				<ul><ul>O(n), n = path length to the replacement</ul></ul><br> 
		PRECONDITION: <br>
		<ul>
			!isEmpty()  
		</ul> */
	public void deleteRoot() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot delete root of an empty tree.");
		
		LinkedBinaryIteratorUos curPos = newIterator();
		deleteItemAt(curPos);
	}
  
	/**	Delete the item in position specified by pos. <br>
		Analysis: Time = O(1) when it has an empty subtree. <br>
				<ul><ul>O(n), n = path length to successor</ul></ul><br>
		@param pos position of the item to be deleted */
	protected void deleteItemAt(LinkedBinaryIteratorUos pos)
	{
		BinaryNodeUos cur, parent, replaceNode;
		boolean foundReplacement = false;	  
		replaceNode = null;
		parent = pos.parent;
		cur = pos.cur;
		if (cur.rightNode()==null)
		{
			replaceNode = cur.leftNode();
			foundReplacement = true;
		}
		else if (cur.leftNode()==null)
		{
			replaceNode = cur.rightNode();
			foundReplacement = true;
		}	  
		if (foundReplacement)
		{
			if (parent==null) 
				setRootNode(replaceNode);
			else if (parent.leftNode()==cur)
				parent.setLeftNode(replaceNode);
			else 
				parent.setRightNode(replaceNode);
		}
		else
		{
			LinkedBinaryIteratorUos replacePos = findReplacementItemPosition(pos);
			cur.setItem(replacePos.item());
			deleteItemAt(replacePos);
		}      
	}

	/**	Find the position of the inorder successor for item in currentLocation. <br>
		Analysis: Time = O(n), where n = path length to successor <br>
		PRECONDITION: <br>
		<ul>
			!((currentLocation.cur==null) || (currentLocation.rightNode()==null))
		@param currentLocation position of the successor item */
	protected LinkedBinaryIteratorUos findReplacementItemPosition(LinkedBinaryIteratorUos currentLocation) throws InvalidArgumentUosException
	{
		if ((currentLocation.cur==null) || (currentLocation.cur.rightNode()==null))
		{
			throw new InvalidArgumentUosException("Need current item and non-empty right subtree.");
		}	
		else
		{
			LinkedBinaryIteratorUos result = (LinkedBinaryIteratorUos)currentLocation.clone();
			result.goRight();
			while (result.cur.leftNode()!=null)
				result.goLeft();
			return result;
	  	}
	}

	/**	Create a cloned version of the tree. <br>
		Analysis: Time = O(n), where n = number of items in the tree */
	public BasicBinaryTreeUos treeClone() 
	{
		BasicBinaryTreeUos result = (BasicBinaryTreeUos)this.clone(); // Shallow clone
		if (rootNode==null)
			return result;
		else
		{
			result.setRootLeftSubtree(((BasicBinaryTreeUos)rootLeftSubtree()).treeClone());
			result.setRootRightSubtree(((BasicBinaryTreeUos)rootRightSubtree()).treeClone());
			return result;
		}
	}

}