594 Assignment 3: Exercises in Recursion
Spring 2006, David Matuszek
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.
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
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
In this case, either the required method or its helper method must be recursive.
Tree is never
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
Your JUnit tests will still have to check, for each method, whether the correct Exception is thrown. Sorry!
static public Tree<?> leftmostDescendant(Tree<?> root)
root. That is, return the leaf that is the first child of the first child of ... the first child of
rootitself is a leaf, return
static public Tree<?> rightmostDescendant(Tree<?> root)
root. That is, return the leaf that is the last child of the last child of ... the last child of
rootitself is a leaf, return
static public int numberOfNodes(Tree<?> root)
static public int depth(Tree<?> root)
static public boolean containsEqualValue(Tree<?> root, Object value)
rootcontains a value that equals the second parameter.
static public boolean containsSameValue(Tree<?> root, Object value)
rootcontains the same object (not just an equal object) as the one given for the
static public Set<Tree<?>> nodesOf(Tree<?> root)
Setof all the nodes in the Tree rooted at
static public Set<?> valuesOf(Tree<?> root)
Setof the values (of type V) in the Tree whose root is at
static public Tree<?> copy(Tree<?> root)
root. Every node in this new Tree will be created by the
copymethod; values will be identical (==) to values in the given Tree.
static public Tree<?> reverse(Tree<?> root)
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
static public void reverseInPlace(Tree<?> root)
rootto be the mirror image of its original structure. No new
Treenodes are created in this process (your JUnit tests should check this). The values in the nodes are unchanged.
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
and so that Eclipse does not give warnings or errors for this or subsequent
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
TreeTest classes, so you are turning in a complete, runnable
program. Use the default package for everything.