CIT 594 Assignment 3: Exercises in Recursion
Spring 2006, David Matuszek

Purposes:

To give you a lot of practice with recursion
To give you more practice with Eclipse and JUnit testing
To give you some practice with the Set class

General Idea:

Using the Tree class defined in the previous assignment, implement a number of recursive methods. Most of these methods will be useless, except as exercises, but some of them may be used in later assignments.

Details:

Create a class named TreeMethods to contain the following methods. For each method, begin by writing a JUnit test method. Then write the method stub, then test your JUnit test and make sure it fails, then write the method.

All public methods should have complete and accurate Javadoc comments. (For the most part you can just copy the comments from this assignment, but be sure to also supply @param, @return, and @throws tags as appropriate.)

All the required methods should be written recursively, even if there is another way to do it. You can use additional helper methods, so long as they are private. In this case, either the required method or its helper method must be recursive.

Note: A Tree is never null, but the value in a Tree node may be null. You will have to be careful of null values in a few of these methods, so write your unit tests accordingly.

I said in class that you should throw an IllegalArgumentException if a null Tree is passed in as an argument. I am changing this requirement. You should instead throw a NullPointerException if a null Tree is passed in as an argument. Why? Because that's what your methods will almost certainly do anyway if given a null Tree. Either exception is just as informative, and the latter doesn't require you to write extra code to check for null Trees.

Your JUnit tests will still have to check, for each method, whether the correct Exception is thrown. Sorry!

static public Tree<?> leftmostDescendant(Tree<?> root): Returns the leftmost descendant of root. That is, return the leaf that is the first child of the first child of ... the first child of root. If root itself is a leaf, return root.

static public Tree<?> rightmostDescendant(Tree<?> root): Returns the rightmost descendant of root. That is, return the leaf that is the last child of the last child of ... the last child of root. If root itself is a leaf, return root.

static public int numberOfNodes(Tree<?> root): Returns the total number of nodes in the Tree whose root is at root (including root itself).

static public int depth(Tree<?> root): Returns the depth of the tree. The depth of a tree is the length of the longest path from the root. The depth of a tree with no descendants is zero.

static public boolean containsEqualValue(Tree<?> root, Object value): Returns true if and only if some node in the Tree whose root is at root contains a value that equals the second parameter.

static public boolean containsSameValue(Tree<?> root, Object value): Returns true if and only if some node in the Tree whose root is at root contains the same object (not just an equal object) as the one given for the value parameter.

static public Set<Tree<?>> nodesOf(Tree<?> root): Returns a Set of all the nodes in the Tree rooted at root.

static public Set<?> valuesOf(Tree<?> root): Returns a Set of the values (of type V) in the Tree whose root is at root.

static public Tree<?> copy(Tree<?> root): Returns a new Tree equal to (but not the same as) root. Every node in this new Tree will be created by the copy method; values will be identical (==) to values in the given Tree.

static public Tree<?> reverse(Tree<?> root): Returns a new Tree which is the mirror image of the Tree whose root is at root. That is, for every node in the new Tree, its children are in reverse order (first becomes last, second becomes next to last, etc.) The values in the nodes are unchanged, that is, not reversed (they are probably not Trees, and probably don't have a reverse method).

static public void reverseInPlace(Tree<?> root): Rearranges the tree rooted at root to be the mirror image of its original structure. No new Tree nodes are created in this process (your JUnit tests should check this). The values in the nodes are unchanged.

In my nodesOf(Tree) method I am using the following declaration:

Set nodes = new HashSet();

There will be a small amount of extra credit for the first person who can tell me how to correctly genericize this set, so that it contains only Trees, and so that Eclipse does not give warnings or errors for this or subsequent statements.

Due date:

Please zip up and turn in your completed program, including all Java source and class files and all Javadoc generated documentation, via Blackboard, before midnight Tuesday, January 31. Include your Tree and TreeTest classes, so you are turning in a complete, runnable program. Use the default package for everything.