For this assignment, you will be extending a provided Graph187 class to create a Tree187 class. You will create new methods, private variables, and so on, to implement the tree, but its underlying data (nodes and edges) will be stored in the Graph187 structure.
Graph187 class (provided to you)
This class is provided for you so that you can understand what it is doing. However, it is sufficient to understand what the classes described in Graph187Interface do. At a high level, for this project, a graph node is a String (its label) and a weight associated with the node. Edges are links between nodes and can also have weights.
The Graph187 class bundles together the label and weight into a "Node" that is stored in a Java-provided HashMap (very much like your QuickStore class in spirit). So if a node/vertex is added, it goes in the HashMap.
There is another HashMap used for storing edges. An edge is also a bundle of the label for the start node, the label for the end node, and the weight of the edge.
In order to place an ordering on the edges that are adjacent to a vertex, a list of incident edges is maintained at each node. The list is an array of Edge's that can be arbitrary large and that can have empty positions. The index values are not particularly important for Graph187 but are helpful for implementing trees.
The following statements would create a small cycle in the Graph187 variable g:
g.addVertex( "one" );
g.addVertex( "two" );
g.addVertex( "three" );
g.addEdge( "one", "two" );
g.addEdge( "two", "three" );
g.addEdge( "three", "one" );
Note that the index values and weights are not used. By default, weights are always 1.0 and index values are the next available index.
If an error occurs (e.g., you try to add a vertex twice) the class throws an InvalidGraphOperation exception.
See the Graph187Interface.java file for more details about the methods.
You may modify Graph187.java or the interface as part of your own testing and debugging. However, your code must work with unmodified versions of both files when you submit them.
Tree187 class (you implement)
Your job is to implement Tree187. It must be designed so that it extends Graph187.
A tree is like a graph but it has restrictions:
A tree must have a special vertex called a root
No vertex can have more than one parent
Only the root can exist with no parent (otherwise it would be a forest and not just a tree)
Cycles are not permitted
Your class must implement Tree187Interface. That includes a few new methods that are documented in the interface file.
In addition, your Tree187 class must prevent someone from performing operations that would violate the properties of a tree. How might that happen? Well, since Tree187 extends Graph187, all of the graph operations are also available. The sequence of six commands above will work just fine, but will create something that isn't a tree if you do not prevent it.
To make that impossible, you will have to override some of the Graph187 methods in your Tree187 class. For example, in that sequence of operations above, the g.addVertex( "two" ) operation should throw an exception because it is not reasonable to have two vertices without a parent: that would make it a forest rather than a tree. Similarly, adding a third edge that creates a cycle would throw an exception because trees do not have cycles.
There is (at least) one tricky aspect to this type of overriding. Suppose you code Tree187's addRoot() method to invoke addVertex(label) of the super class. If you look in Graph187.java, you'll see that addVertex(label) invokes Graph187's addVertex(label,weight). Perhaps surprisingly, if that is being invoked on a Tree187, it will run the addVertex(label,weight) method of the tree rather than the graph! To get around that, in Tree187.java, only call Graph187 methods that do not turn around and call other Graph187 methods that are overridden by a Tree187 method. In this case, if addRoot() invokes addVertex(label,weight) in the superclass, all is well.
Some things to note:
An "in order" traversal of an arbitrary tree (where a node can have any number of children) is not well defined. For this assignment, assume that means to traverse the left-most child, then the node, and then the rest of the children. That makes it consistent with an "in order" traversal of a binary tree.