About Schedule Software

SA-7, due Oct 16

Recitation section will be helpful for this short assignment

This Short Assignment requires you to write a couple of recursive methods on trees. The section leaders will discuss two specific examples which will be very helpful in writing these methods. So be sure to go to your section. Also, writing recursive methods is important for the midterm coming up.

Assignment

In this assignment you will add two utility methods to BinaryTree.java. The header of the first is:

	/**
	 * Counts the number of leaf nodes in this tree
	 * @return the number of leaf nodes in this tree
	 */
	public int countLeaves() 

The header of the second is:

	/**
	 * Make a shallow copy of this tree.  (By shallow, we mean that
	 * the data items are linked and not copied.  Thus, for instance,
	 * if the method getValue() is called on the root of this tree
	 * and on the root of the copy of the tree, the method will return 
	 * reference to the same object.
	 * @return a shallow copy of this tree.
	 */
	public BinaryTree<E> copyTree() {

In both cases you should write a recusive function. Be sure to see the methods already in BinaryTree for examples that do the sorts of things that your code will need to do. (Note - you should NOT implement copyTree by doing traversals and then calling reconstructTree. The equals method might be a better place to look for inspiration.)

I say to make a "shallow copy". That means that all of the tree nodes are copied, but the data values (returned by calling getValue()) are not copied. They are shared and referenced by a node in the old tree and a node in the new tree. Thus, for example, the root nodes of the two trees will be different, so performing a setValue(newValue) on the root of the copy will not change the original. However, the elements are aliased. Therefore if the data were a Counter object, calling root().getValue().tick() on the copy will mean that the counter in the root of the original will also change its value, because it is the same counter.

Testing

Test your code by modifying the main method of BinaryTree.java

Try to create a convincing set of tests.

Extra Credit

The reconstructTree method in BinaryTree is not very efficient. It repeatedly re-copies sublists of the input lists to new lists to pass to the recursive calls.

It is possible to avoid all of this recopying by passing the original preorder and postorder lists to recursive calls. You specify the desired sublist by passing additional parameters that say where in the list the desired sublist begins and ends. So you can overload reconstructTree by writing a 6-parameter version, with 2 lists and a range specification for each.

Add this version of reconstructTree to BinaryTree.

Blackboard submission

Submit via Blackboard the zip file of a folder that contains (1) your file BinaryTree.java that contains the two utility methods you wrote, in addition to all else that was in it originally, and (2) output of your test runs that demonstrate your methods.