Purposes:

• To give you some experience writing generic classes and methods.
• To give you a lot of practice with recursion.
• To give you some practice with the Set collection.

General Idea:

Back before Java had generics, I defined a BinaryTree class. Your job is to:

• Genericize this class and the methods in it, and
• Implement a number of additional recursive methods. Some of these methods may be used in later assignments.

Details:

Supplied code: BinaryTree.java and BinaryTreeTest.java.

You will first need to "genericize" the BinaryTree class. Begin by changing

public class BinaryTree {
    public Object value;
    private BinaryTree leftChild;
    private BinaryTree rightChild;

public class BinaryTree<V> {
    public V value;
    private BinaryTree<V> leftChild;
    private BinaryTree<V> rightChild;

Add the following methods to the BinaryTree class. 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. Do not use loops. 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.

In most implementations of binary trees, you can only go down, to children; there is no way to go up, to a parent. (Of course, you could define a node in a binary tree to have a reference to its parent as well as to its left and right children; I'm just saying this isn't usually done.) So every node (that is, every instance of the BinaryTree class) can be considered to be the root of a binary tree. In order to understand the following methods, you must understand that every instance of BinaryTree can be thought of as a single node, or as the root node of a binary tree, or as representing the entire binary tree rooted at this node. Binary trees are composed of binary trees.

Thus, for example, one method you will be asked to write is numberOfNodes, which returns how many nodes there are in this binary tree, in other words, in the entire binary tree rooted at this node. If this binary tree occurs as part of some other binary tree, that fact is irrelevant; only this node and its descendents are reachable, and anything unreachable is irrelevant.

Note: A binary tree may be null. One or both of the children of a binary tree may be null. In most cases, this is perfectly acceptable; if there are any cases where it isn't, your method should throw a NullPointerException.

Note: Set and List are interfaces, not classes; but you can create instances of HashSet and ArrayList.

public BinaryTree<V> leftmostDescendant()

Returns the leftmost descendant of this binary tree. That is, return the leaf that is the left child of the left child of ... the left child of this binary tree. If this binary tree has no left child, return this binary tree.

 

public BinaryTree<V> rightmostDescendant()

Returns the rightmost descendant of this binary tree. That is, return the leaf that is the right child of the right child of ... the right child of this binary tree. If this binary tree has no right child, return this binary tree.

 

public int numberOfNodes()

Returns the total number of nodes in this binary tree (include the root in the count).

 

public int depth()

Returns the depth of this binary tree. The depth of a binary tree is the length of the longest path from this node to a leaf. The depth of a binary tree with no descendants (that is, just a leaf) is zero.

 

public boolean containsEqualValue(V value)

Returns true if and only if some node in this binary tree contains a value that is equal to the parameter.

 

public boolean containsSameValue(V value)

Returns true if and only if some node in this binary tree contains the same object (not just an equal object) as the one given for the value parameter.

 

public Set<BinaryTree<V>> leaves()

Returns a Set of all the leaves of this binary tree.

 

public Set<V> valuesOf()

Returns a Set of the values (of type V) in this binary tree.

 

public List<V> fringe()

Returns a List of the values (of type V) in the leaves of this binary tree, in left-to-right order.

 

public BinaryTree<V> copy()

Returns a new BinaryTree equal to (but not the same as) this binary tree. Every node in this new BinaryTree will be created by the copy method; values will be identical (==) to values in the given binary tree.

 

public BinaryTree<V> reverse()

Returns a new binary tree which is the mirror image of the binary tree whose root is at this binary tree. That is, for every node in the new binary tree, its children are in reverse order (left child becomes right child, right child becomes left child).

 

public void reverseInPlace()

Rearranges the binary tree rooted at this binary tree to be the mirror image of its original structure. No new BinaryTree nodes are created in this process.

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 Thursday, February 7. The name of your zip file should include some part of your name and the name of this assignment, for example, JohnSmith_Recursion.zip.