Implement Tree Data Structures

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

• AbstractTree.java: abstract class as described in part (1)
• BasicTree.java: class implementing AbstractTree as described in part (2)
• SortedTree.java class implementing AbstractTree as described in part (3)

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.

Part 1: Abstract class AbstractTree

Combine the Tree and AbstractTreeNode so that

• AbstractTreeNode is a nested class of AbstractTree
• AbstractTree and AbstractTreeNode are generic

Part 2: BasicTree Class

Write a class BasicTree that extends the AbstractTree from part 1.

• The class that extends AbstractTreeNode should be called BasicTreeNode and should store the offspring in an unsorted list.
• Implement all the interface methods for AbstractTreeNode. You should implement isDescendant recursively.
• Make BasicTree implement the interface Iterable, and define the default Iterator as breadth first, with next() returning the elements. Write a second private breadth first iterator that does the same, but where next() returns TreeNodes.
• Write a third iterator that iterates over the elements in reverse order (to show you can!)
• Implement all the methods specified in the class AbstractTree (using your Iterator where appropriate).
• Write a constructor that takes a TreeNode and a toString method that prints out the whole tree
• Write a main method that demonstrates that your solutions to (1)-(6) work by printing out relevant information to the console so that I can black box test it.

Part 3: SortedTree Class

• Write an new class SortedTree that also extends your AbstractTree so that
  • The elements of the SortedTree must be Comparable.
  • The offspring in a node must be stored in sorted order (define a new class extending AbstractTreeNode).
• Implement all the methods described in points (2)-(6) of part 2. Methods to add an element or tree should maintain sorted order of the offspring, and Iterators should traverse offspring in sorted order.
• Make your class extend the AbstractCollection as a modifiable collection, where method add simply adds the element at the root of the tree (see the API for details).
• Make the class Serialisable and allow for the saving and loading of a tree.
• Implement a second Iterator that traverses the tree in depth first order. Set the choice of Iterator through an enum type.
• Construct an experiment to estimate the time complexity of contains() for both BasicTree and SortedTree over a range of tree sizes.
• Write a main method that demonstrates that your solutions to these questions work by printing out relevant information to the console so that I can black box test it.

TREES

Tree data structures are common. Family trees and evolutionary (phylogenetic) trees are two common examples. See image.

General points about trees

• A tree is a special form of graph where circular references are not allowed
• The end nodes of a tree are often called leaf nodes.
• A heap is a special form of tree that can be stored in an array. In java, a heap is provided by the PriorityQueue class.
• A trie is a special form of tree (commonly called a prefix tree) where the position in the tree defines the key it is associated with.
• A binary tree is a special kind of tree with at most two offspring per node.
• A binary search tree is a special kind of binary tree is where the elements are sorted.
• A self balancing binary search tree is a binary search tree that automatically keeps its height to a minimum in the face of arbitrary item insertions and deletions.
• A B-tree is a sorted tree (i.e. it can have more than two offspring). Note that the solution to part 3 is not a B-tree, since we do not sort the elements between levels.

Notes 1: BasicTreeNode

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

• abstract public void add(Object child);
• abstract public void add(AbstractTreeNode child);
• abstract boolean remove(E child);
• abstract boolean remove(AbstractTreeNode child);
• abstract public boolean isChild(Object child);
• abstract public AbstractTreeNode getChild(Object child);
• abstract public boolean isDescendant(Object child);
• abstract public AbstractTreeNode get(Object child);

(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.

Notes 2: BasicTree

You have to implement the following methods.

• abstract public int size();
• abstract public boolean contains(E element);
• abstract public boolean add(E parent, E child);
• abstract public boolean add(E parent, AbstractTreeNode child);
• abstract public boolean remove(E element);
• abstract public boolean remove(AbstractTreeNode element);
• abstract public boolean add(E parent, Tree child);
• abstract public Tree subTree(E parent);

(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.