CIT 594 Assignment 1: Tree API
Spring 2009, David Matuszek

Purposes of this assignment:

General idea of the assignment:

A tree is a data structure composed of nodes, where each node contains a value of some arbitrary type, and a list of zero or more children, each of which is also a node. In this data structure, essentially each node is a tree.

In this assignment you are to build a simple Tree API. This API will enable you to create trees, read and write trees, and do basic navigation.


This will be a genericized class--that is, when you construct a tree, you specify the type of values it can hold.

public class Tree<V> {...}
Here is the one constructor you need:
public Tree<V>(V value) (Eliminate the <V> here)
Creates a tree consisting of a single node, having the given value. It should also create an empty ArrayList to hold its (future) children.
Here are the required methods:
public Tree<V> addChild(Tree<V> child) throws IllegalArgumentException
Adds the given Tree child as the new last child of this Tree.

You need to write this method very early, because without it you will only be able to create single-node trees. However, you can't really test it until you have the next method (equals) also written.

Don't worry about throwing an IllegalArgumentException until after you have written and tested the contains method. Once that is done, come back and modify this method to throw the exception when tree1.addChild(tree2) is called, and tree2.contains(tree1). This would create a loop, or cycle, in the Tree, which is illegal.
public Tree<V> addChild(V value) throws IllegalArgumentException
A simple convenience method for addChild(new Tree(value)).
public boolean equals(Object obj)
Tests whether this Tree is equal to the given Object; returns false if the Object is not a Tree.

This is a highly recursive method. Two trees are equal if their values are equal (according to their equals method), and they have the same number of children and all their children are equal and in the same order.

It is important to write this method early, and test it thoroughly, so that you can use it in JUnit tests of the other methods.
public String toString()
Returns a String representation of this Tree, with the format
     value(child_1 child_2 ... child_N)

Sometimes people try to JUnit test whether Trees (or other data structures) are as expected by comparing their String representations. Don't do this! (1) It ties you to a very specific String representation, and (2) it's wrong anyway, since different values (such as 2 and '2') can have the same String representation.
public List<Tree<V>> children()
Returns the ordered list of the children of this Tree. (This is a one-line method.)
public Iterator<Tree<V>> iterator()
Returns the iterator for the list of children of this Tree. (One line.)
public void setValue(V value)
Sets the value field in this Tree, that is, the value in the root). (One line.)
public V getValue()
Returns the value in this Tree, that is, the value in the root. (One line.)
public static Tree<V><String> parse(String s)
Returns a Tree corresponding to the given String. All values in the resultant Tree will be of type String.

This is the most difficult method. Here's my suggested approach: Use a StringTokenizer to get "tokens" from the input string. Use the settings
        new StringTokenizer(s, " ()", true)
this will return parentheses, spaces, and "words" (not containing spaces or parentheses) as "tokens". Discard the spaces and put the remaining tokens into an ArrayList. Pass this list to a second (private) parse method. This method should do something approximately as follows:
Get a value for the root (or return null)
If there is an open parenthesis,
    Parse each tree inside the parentheses and add it to the root
    Get the close parenthesis
Return the tree
public void print()
Prints the tree, in indented, multi-line format. Since this is an output method, it does not require JUnit testing. This method should also be recursive.
public boolean contains(Tree<V> tree)
Tells whether this Tree contains the identical (in the == sense) node as the given tree. This method should also be recursive.


Given this Tree: toString() should return:
one(two three(four five(six seven eight)))
A tree print() should print:
|  two
|  three
|  |  four
|  |  five
|  |  |  six
|  |  |  seven
|  |  |  eight

Structure of the assignment:

The above are requirements. You may have additional classes and methods as needed, and they should be documented and unit tested as appropriate.


Your methods will be tested with my JUnit tests. In addition, your JUnit tests will be used to test my Tree methods (some of which will contain deliberate errors).

Due date:

Thursday, January 22, before midnight. Zip the complete Eclipse project and submit via Blackboard.