This exercise is designed to test you understanding of the following topics Inheritance (L1), Nested Classes+Enum (L2), Generics (L3), Collections (L4), Serialization (L5), Binary Tree (L6).
The Collections hierarchy contains implementations for Lists (ArrayList, LinkedList), Binary Search Trees and Sets (TreeMap and TreeSet) and Hash Tables (HashSet and HashMap). The obvious absence is a general Tree class. Tree data structures are common and useful. Hence, your exercise is to implement a Tree class within the collections hierarchy.
I have provided an interface Tree.java and an abstract class AbstractTreeNode.java
You have to submit three classes for the coursework
Note you must base your solution on my interfaces and implement the tree in the way described. The way I have structured this code is not the only way of doing it, and possibly not the best way. I have done it this way to test your understanding of features of the language, so you may be marked down if you do not follow the recommended structure.
There are tree implementations online, and it may be helpful to look at them, but they will be noticeably different to the one I am recommending. If you simply reproduce someone else’s code it will be obvious. Please note we take plagiarism very seriously. We reserve the right to call you in to explain your solution to us in person and if you are unable to do so we will consider this evidence of possible plagiarism. We want to test whether you understand the features in java we teach on the course, and if you copy you clearly don’t understand it! Please comment your code and remove auto generated comments if not appropriate.
I have asked for a test harness for solutions to (2) and (3) and have been intentionally vague about what is required. It is up to you to develop clear ways of testing your code. Ideally, your test harness should be interactive, but a GUI is not required.
Combine the Tree and AbstractTreeNode so that
Write a class BasicTree that extends the AbstractTree from part 1.
Tree data structures are common. Family trees and evolutionary (phylogenetic) trees are two common examples. See image.
General points about trees
So given a tree See image.
the root node would contain the element A and a collection of nodes . You have the following methods to implement
(note the signatures will change when you complete part 1) add simply adds to the offspring list. Adding “H” to the node containing “A” add a node “H” with two offspring “I” and “J” See image.
isChild and getChild simply scan the direct offspring of the node. So isChild(“B”) is true for the node containing “A”, but isChild(“E”) is false. isDescendant and getDescendant scan the whole descendant list. So both isDescendant (“B”) and isDescendant (“E”) are true. The iterator for the node should not be recursive. So to iterate across the node containing A in Fig 1, you would return B, C and D only, and to do the same with the tree in Fig 2 and Fig 3 would give B,C,D,H in both cases. You can use built in iterators for this if appropriate.
You can of course add any other helper methods you require, but be sure to comment them well.
You have to implement the following methods.
(note the signatures will change when you complete part 1) All of these can be easily implemented with a combination of the methods for TreeNode and an Iterator for BasicTree (see comments in the provided code), so try first to make the BasicTree Iterable.
There are basically two ways of iterating over a tree: breadth first and depth first.
You have seen a depth first traversal of binary trees (in-order, pre-order and post-order). So a depth first pre-order iteration of the tree above would give A-B-E-F-C-D-G. Depth first is implemented with the help of a Stack (last- in, first-out).
A breadth first iteration goes level by level. So a breadth first traversal would give A-B-C-D-E-F-G. Breadth first can be implemented with the use of a Queue (first-in, last-out).
You start by adding the head TreeNode to the queue.
When next() is called, you recover the item at the front of the queue, add all that items offspring to the back of the queue, then return the item. Google to find out more, there is a wiki page here http://en.wikipedia.org/wiki/Tree_traversal#Breadth-first_Traversal There is no explicit Queue class in Java, so you should use your own. I recommend using an appropriate LinkedList.