exampletree.java

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

import dslib.base.*;
import dslib.tree.*;

/**	A tree class with several methods showing the use of traversals
	to accomplish tasks. */
public class ExampleTree extends LinkedSimpleTreeUos
{
	/**	Constructor of the class. */
	public ExampleTree(){}
	
	public ExampleTree(ExampleTree lt, Object r, ExampleTree rt)
	{
		super(lt, r, rt);
	}
	
	/**	The number of nodes in the tree.
		Analysis: Time = O(number of nodes in the tree) */
	public int size()
	{
		if (isEmpty())
			return 0;
		else
		{
			int result;
			int leftSize = ((ExampleTree) rootLeftSubtree()).size(); 
			int rightSize = ((ExampleTree) rootRightSubtree()).size();
			result = 1 + leftSize + rightSize; 
			return result;
		}
	}

	/**	The height, i.e., the number of levels of the tree.
		Analysis: Time = O(size of the tree) */
	public int height()
	{
		if (isEmpty())
			return 0;
		else
		{
			int result;
			int leftHeight = ((ExampleTree) rootLeftSubtree()).height();
			int rightHeight = ((ExampleTree) rootRightSubtree()).height();
			result = 1 + Math.max(leftHeight, rightHeight);
			return result;
		}
	}

	/**	The number of leaves in the tree.
		Analysis: Time = O(size of the tree) */
	public int numberOfLeaves()
	{
		if (isEmpty())
			return 0;
		else if (rootLeftSubtree().isEmpty() && rootRightSubtree().isEmpty())
			return 1;
		else
		{
			return ((ExampleTree) rootLeftSubtree()).numberOfLeaves()
				+ ((ExampleTree) rootRightSubtree()).numberOfLeaves();
		}
	}

	/**	The sum of the values in the tree.
		Analysis: Time = O(size of the tree) */
	public int sum()
	{
		if (isEmpty())
			return 0;
		else
		{
			return ((Integer) rootNode.item()).intValue() 
				+ ((ExampleTree) rootLeftSubtree()).sum()
				+ ((ExampleTree) rootRightSubtree()).sum();
		}
	} 

	/**	The maximum imbalance value of the tree (naive algorithm). */
	public int maxImbalIneff()
	{
		int leftImbalance, rightImbalance, myImbalance;
		
		if (isEmpty())
			return 0;
		else
		{
			int result = 0;
			myImbalance = Math.abs(((ExampleTree) rootLeftSubtree()).height() 
						- ((ExampleTree) rootRightSubtree()).height());
			leftImbalance = ((ExampleTree) rootLeftSubtree()).maxImbalIneff();
			rightImbalance = ((ExampleTree) rootRightSubtree()).maxImbalIneff();
			result = Math.max(myImbalance, Math.max(leftImbalance, rightImbalance));
			return result;
		}
	}
	
	/**	Return a pair of integers. The first integer is the height of the current tree
		and the second integer is the maximum imbalance of the current tree. */
	public PairUos helpMaxImbal()
	{
		PairUos li, ri, result;
		int myImbalance;

		result = new PairUos(new Integer(0), new Integer(0));
		if (!isEmpty())
		{
			li = ((ExampleTree) rootLeftSubtree()).helpMaxImbal();
			ri = ((ExampleTree) rootRightSubtree()).helpMaxImbal();
			int leftHt = ((Integer) li.firstItem()).intValue();
			int rightHt = ((Integer) ri.firstItem()).intValue();
			result.setFirstItem(new Integer(Math.max(leftHt, rightHt) + 1));
			myImbalance = Math.abs(leftHt - rightHt);
			int leftImbal = ((Integer) li.secondItem()).intValue();
			int rightImbal = ((Integer) ri.secondItem()).intValue();
			result.setSecondItem(new Integer(Math.max(myImbalance,
						Math.max(leftImbal, rightImbal))));
			return result;
		}
		return result;
	}

	/**	The maximum imbalance value of the tree. */
	public int maxImbal()
	{
		return ((Integer) helpMaxImbal().secondItem()).intValue();
	}
}