CIT 594 Assignment 3: A Tree ADT
Spring 2014, David Matuszek
Your assignment is to:
An ADT has a contract with its users, which is specified
by its public members and described via Javadoc. It provides certain operations,
and restricts access to only those operations. Your
is such an ADT. In addition, any ADT is responsible for ensuring the validity of its data.
In this assignment, you are to take that responsibility very, very seriously
A tree is composed of nodes. Each node has a value, and may have
Tree class will be genericized (have a type parameter) so that you
can specify the type of values in the nodes; the children will be (references
Your assignment is to define the following classes and methods.
public class Tree<V>
This is your ADT class. Each object in the
Tree class represents
a single node; however, nodes are linked together in such a way that any node may be considered
as the "root" of a complete tree. In the following, the terms "node"
and "Tree" are synonyms, but I tend to use "node" when I'm
talking about one specific object of type
Tree, and "Tree"
when I'm referring to that node and all its descendents (children, children
of children, etc.).
Treeclass should have the following constructor:
public Tree(V value, Tree<V>... children)
Treenode with the given
valueand zero or more
..." syntax means that you can call the constructor with
new Tree<type>(v), or
new Tree<type>(v, c1), or
new Tree<type>(v, c1, c2), or
new Tree<type>(v, c1, c2, c3), etc., but when you write the code inside the constructor, you write it as if it were defined as
Tree(V value, Tree<V> children).
Tree class should have the following methods:
An accessor is a method that returns some information about the data type.
public V getValue()
public Tree<V> firstChild()
nullif this tree is a leaf).
public Tree<V> lastChild()
nullif this tree is a leaf).
public int numberOfChildren()
public Tree<V> child(int index) throws NoSuchElementException
index-th child of this tree (counting from zero, as with arrays). Throws a
indexis less than zero or greater than or equal to the number of children.
public Iterator<Tree<V>> children()
remove()methods, all of which should be implemented. (Hint: Java's
ArrayListalready provides an iterator.)
public boolean isLeaf()
falseif this node has children. This is a convenience routine: The user could just test
node.numberOfChildren() == 0instead.
private boolean contains(Tree<V> node)
trueif this tree contains the given node (not an equal node; use
equals). The root of this tree is included in the recursive search.
@Override public boolean equals(Object object)
Tree, and (2) the
valuefields of the two trees are equal, and (3) each child of one Tree
equalsthe corresponding child of the other Tree.
==, while non-null objects must be compared using
equals(Object), and (2) this method is recursive. You will need this method in order to do unit testing on your Tree class.
public String toString()
toString()representation of the value in that node, terminated with a newline (
\n). Each child is indented two spaces under its parent. For example:
one two five three four six seven
|The result of calling
"one\n two\n five\n three\n four\n six\n seven\n"
A transformer is one that, applied to a data structure, produces a different data structure. A mutative transformer is one that changes the data structure to which it is applied (for example, the
add method of the
ArrayList class). An applicative transformer is one that produces a new data structure of the same kind (for example, the
toLowerCase method of the
public void setValue(V value)
public void addChild(Tree<V> newChild) throws IllegalArgumentException
newChildas the new last child of this tree, provided that the resultant tree is valid (see below). If the operation would result in an invalid tree, the tree is unchanged and the method throws an
public void addChild(int index, Tree<V> newChild) throws IllegalArgumentException
newChildas the new
index-th child of this tree (counting from zero), provided that the resultant tree is valid (see below). The child previously at this index, and all subsequent children, are "shifted right" (their index is increased) to make room for the new child. If the index is less than zero or greater than (not greater than or equal to) the current number of children, or if the operation would result in an invalid tree, the tree is unchanged and the method throws an
public void addChildren(Tree<V>... children ) throws IllegalArgumentException
childrenas a new child of this tree node, after any existing children, provided that the resultant tree is valid (see below). If the the addition of any child node would result in an invalid tree, that node is not added, tree modification is halted, and the method throws an
public Tree<V> removeChild(int index) throws NoSuchElementException
index-th child of this tree, or throws a
indexis illegal. (This method, and the
remove()method of the above Iterator, simply remove the child from the list of children of this tree; no major tree surgery is involved. The removed subtree remains intact.)
A tree will be considered valid if there are no loops in it. If, starting
from some node in the tree and following child links you can get back to the
same node, then there is a loop and the tree is invalid. You need to
test for validity in the
Child methods. We will,
however, allow subtrees to be shared, provided there are no loops.
Before adding a node
child as a new
child of node
parent (each of which may be inside some tree structure),
test if node
parent occurs in the tree whose root is
If it is, do not perform the operation,
but instead throw an
IllegalArgumentException instead. Note that
(1) the tests must search for identical (
==) nodes, not just equal
ones, and (2) the search is inherently recursive.
You will need the
contains method to implement the validity test.
Since this search method will be private, you cannot test it explicitly--rather,
you test it implicitly, by making sure that your
will throw an exception when asked to construct an invalid tree.
Shared subtrees are occasionally useful. For example, if you were to evaluate the tree equivalent of the expression
(x - y) * (x - y), you might be able to do so in such a way that you evaluate
(x - y) only once.
Usually, however, trees are defined in such a way that shared subtrees are not allowed. Furthermore, I do not expect to make use of shared subtrees in this course. However, while it is fairly simple to do a recursive search to disallow loops in a tree, it is much more difficult to detect (and disallow) shared subtrees. Since shared subtrees are generally harmless, it is easier to allow them than to try to prevent them.
public class TreeTest
As part of the assignment, write, use, and turn in a JUnit test class for the
Tree class. Be thorough, and don't forget to test that exceptions
are thrown when they should be.
When grading your program, we will use our own JUnit tests, as well as or instead
of yours, so be sure to follow the above specifications exactly. Be especially
careful that your
toString() has the correct spaces and newlines.
The best way to keep the children of a node is probably in an
If a node has no children, your code will probably be simpler with an empty
ArrayList than with a
null value for children.
toString() methods, and the
search method you use to look for potential loops, must be recursive. You may
not use a
or similar data structure, to implement these methods.
You are expected to use TDD (Test-Driven Development). This means:
Write stubs for all the methods. (Methods which return a value should
return the value that is most likely to be wrong.)
To get started, you first need to write the constructor, and you need to write the
equals method. After that, it's best to build up the methods and their tests a little at a time; for example, you will probably want to write the
addChild method fairly early, but you can't test whether it correctly throws an
IllegalArgumentException until you have also written the
contains method. Doing things a little at a time this way is almost sure to reduce the amount of time required to write and debug the program.
Turn your assignment in to Canvas before 6 a.m. Thursday, February 6. Late programs, even if only a minute late, will be penalized 10 points for the first week. Programs later than a week may or may not be accepted for grading.