binarynodeuos.java

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

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

package dslib.tree;

/**	A node for use in binary trees.  It has references to left and right nodes, and 
	methods to set the item or set either adjacent node.  The toString function provides 
	an inorder string representation of the tree with the current node as the root. */
public class BinaryNodeUos implements Cloneable
{
	/**	Contents of the node. */
	protected Object item;

	/**	The right node. */
	protected BinaryNodeUos rightNode;

	/**	The left node. */
	protected BinaryNodeUos leftNode;

	/**	Construct a new node with item x. <br>
		Analysis: Time = O(1) 
		@param x the item placed in the new node */
	public BinaryNodeUos(Object x)
	{
		item = x;
	}

	/**	Contents of the node. <br>
		Analysis: Time = O(1) */
	public Object item()
	{
		return item;
	}

	/**	The right node. <br>
		Analysis: Time = O(1) */
	public BinaryNodeUos rightNode()
	{
		return rightNode;
	}

	/**	The left node. <br>
		Analysis: Time = O(1) */
	public BinaryNodeUos leftNode()
	{
		return leftNode;
	}

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

	/**	Set item equal to x. <br>
		Analysis: Time = O(1) 
		@param x item to become the current node's item */
	public void setItem(Object x)
	{
		item = x;
	}

	/**	Set leftNode equal to x. <br>
		Analysis: Time = O(1) 
		@param x node to become the current node's leftNode */
	public void setLeftNode(BinaryNodeUos x)
	{
		leftNode = x;
	}

	/**	Set rightNode equal to x. <br>
		Analysis: Time = O(1) 
		@param x node to become the current node's rightNode */
	public void setRightNode(BinaryNodeUos x)
	{
		rightNode = x;
	}

	/**	Infix order string representation suitable for output. <br> 
		Analysis: Time = O(n), where n = number of nodes linked from this node */
	public String toString()
	{
		String result = new String();
		if (leftNode != null)
			result += leftNode;

		result += item + " ";

		if (rightNode != null)
			result += rightNode;

		return result;
	}
}