linkedsimpletreeuos.java

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

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

package dslib.tree;

import dslib.exception.*;

/**	An implementation of the SimpleTreeUos interface with functions to access and 
	set the root node and the root subtrees.  It also has functions to 
	access the root item, test for empty, and to wipe out all the items. */
public class LinkedSimpleTreeUos implements SimpleTreeUos
{
	/**	Root node of the tree. */
	protected BinaryNodeUos rootNode;

	/**	Create an empty tree. <br>
		Analysis: Time = O(1) */
	public LinkedSimpleTreeUos()
	{
		rootNode = null;
	}

	/**	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 item
		@param rt tree to initialize as the right subtree */
	public LinkedSimpleTreeUos(LinkedSimpleTreeUos lt, Object r, LinkedSimpleTreeUos rt) 
	{	
		rootNode = createNewNode(r);
		setRootLeftSubtree(lt);
		setRootRightSubtree(rt);
	}

	/**	Create a new node that is appropriate to this tree.  This method should be
		overidden for classes that extend this class and need a specialized node,
		i.e., a descendant of BinaryNodeUos. <br>
		Analysis: Time = O(1) */
	public BinaryNodeUos createNewNode(Object item)
	{
		return new BinaryNodeUos(item);
	}

	/**	Is the tree empty?. <br>
		Analysis: Time = O(1)  */
	public boolean isEmpty()
	{
		return rootNode == null;
	}

	/**	Is the tree full?. <br> 
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return false;
	}

	/**	Return the root node. <br>
		Analysis: Time = O(1) */
	protected BinaryNodeUos rootNode()
	{
		return rootNode;
	}

	/**	Set root node to new node. <br>
		Analysis: Time = O(1) 
		@param newNode node to become the new root node */
	protected void setRootNode(BinaryNodeUos newNode)
	{
		rootNode = newNode;
	}

	/**	Contents of the root item. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty()
		</ul> */
	public Object rootItem() throws ContainerEmptyUosException
	{
		if (isEmpty()) 
			throw new ContainerEmptyUosException("Cannot access the root of an empty tree.");
		
		return rootNode.item();
	}

	/**	Set contents of the root to x. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> 
		@param x item to become the new root item */
	public void setRootItem(Object x) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set the root of an empty tree.");
		
		rootNode.setItem(x);
	}

	/**	Left subtree of the root. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public SimpleTreeUos rootLeftSubtree() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return a subtree of an empty tree.");	
		
		LinkedSimpleTreeUos result = (LinkedSimpleTreeUos)this.clone();
		result.setRootNode(rootNode.leftNode());
		return result;
	}

	/**	Right subtree of the root. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> */
	public SimpleTreeUos rootRightSubtree() throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot return a subtree of an empty tree.");	
		
		LinkedSimpleTreeUos result = (LinkedSimpleTreeUos) this.clone();
		result.setRootNode(rootNode.rightNode());
		return result;
	}

	/**	Set the left subtree to t (set isEmpty if t == null). <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!isEmpty() 
		</ul> 
		@param t tree to become the rootLeftSubtree() */
	public void setRootLeftSubtree(LinkedSimpleTreeUos t) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set subtree of an empty tree.");
		
		if (t != null)
			rootNode.setLeftNode(t.rootNode);
		else
			rootNode.setLeftNode(null);
	}

	/**	Set the right subtree to t (set isEmpty if t == null). <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		 <ul>
			!isEmpty() 
		</ul> 
		@param t tree to become the rootRightSubtree() */
	public void setRootRightSubtree(LinkedSimpleTreeUos t) throws ContainerEmptyUosException
	{
		if (isEmpty())
			throw new ContainerEmptyUosException("Cannot set subtree of an empty tree.");
		
		if (t != null)
			rootNode.setRightNode(t.rootNode);
		else
			rootNode.setRightNode(null);
	}

	/**	Remove all items from the tree. <br>
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		setRootNode(null);
	}

	/**	Form a string representation that includes level numbers. <br>
		Analysis: Time = O(n), where n = number of items in the (sub)tree  */
	protected String toStringByLevel(int i) 
	{
		StringBuffer blanks = new StringBuffer((i - 1) * 5);
		for (int j = 0; j < i - 1; j++)
			blanks.append("     ");
	  
		String result = new String();
		if (!isEmpty() && (!rootLeftSubtree().isEmpty() || !rootRightSubtree().isEmpty()))
			result += ((LinkedSimpleTreeUos)rootRightSubtree()).toStringByLevel(i+1);
		
		result += "\n" + blanks + i + ": " ;
		if (isEmpty())
			result += "-";
		else 
		{
			result += rootItem();
			if (!rootLeftSubtree().isEmpty() || !rootRightSubtree().isEmpty())
				result += ((LinkedSimpleTreeUos)rootLeftSubtree()).toStringByLevel(i+1);
		}
		return result;
	}

	/**	String representation of the tree, level by level. <br>
		Analysis: Time = O(n), where n = number of items in the tree */
	public String toStringByLevel()
	{
		return toStringByLevel(1);
	}

	/**	String containing an inorder list of the items of the tree. <br>
		Analysis: Time = O(n), where n = number of items in the tree */
	public String toString()
	{
		if (isEmpty())
			return "";
		else
			return rootNode().toString();
	}

	/**	A clone of this tree. <br>
		Analysis: Time = O(1) */
	public Object clone()
	{
		try
		{
			return super.clone();
		} catch(CloneNotSupportedException e)
		{
			/*	Should not occur: SimpleListUos extends Cloneable and Object implements clone(). */
			e.printStackTrace();
			return null;
		}
	}
}