CS Data Structures Assignment 5 Solved

Tleft    Tmiddle    Tright

When implementing this class, you may use the BinaryTree source code provided (pack-age cs445.binary) as a starting point, or you can start from scratch. You are also al-lowed to use any classes from the Java Collections Framework such as java.util.Stack or java.util.LinkedList (these may be useful, e.g., in implementing tree traversal iterators), but you may not use any Java-provided tree-like structures (e.g., javax.swing.tree.TreeNode).

    • Provided  les

First, carefully read the provided    les, in the usual place on Pitt Box.
The cs445.binary package contains the textbook’s implementation of a binary tree. The cs445.StackAndQueuePackage provides the textbook’s implementations of Stack and

Queue ADTs, which are used in the binary tree implementation (in particular, for the tree iterators).

TernaryTreeInterface and its superinterfaces are provided in the cs445.a5 package. Do not modify these provided les.



1

    • Tasks

You must develop a class named TernaryTree that implements the interface TernaryTreeInterface. You may want to develop a TernaryNode class to represent the nodes of the tree, similar to the BinaryNode class discussed in the textbook and in lecture. As noted above, you may (but are not required to) use the source code provided with the textbook as a starting point.

When storing the children of a node, you must use an array of node references, not three stand-alone instance variables. You can create such an array, e.g., using the following line of code. Please review type erasure if this line is unclear.

@ S u p p r e s s W a r n i n g s ( " u n c h e c k e d " )

TernaryNode <T >[]    chi ldre n  =  ( TernaryNode <T >[]) new    TernaryNode <? >[3];

In this example, children[0] represents the left child, children[1] the middle child, and children[2] the right child.

The TernaryTreeInterface declares the abstract methods that are speci c to the ternary tree, and also inherits the abstract methods of TreeInterface and TreeIteratorInterface. Thus, when implementing TernaryTreeInterface, you will also need to override the abstract methods declared in both of these superinterfaces.

TreeInterface declares basic tree operations such as getHeight, getNumberOfNodes, etc. TreeIteratorInterface declares methods that create and return iterators for performing

various traversals of the tree. Your TernaryTree class must include the following in-ner classes that implement these iterators: PreorderIterator, PostorderIterator, and
LevelOrderIterator.
Your iterators do not need to support the remove() operation (recall that this operation is

optional). That is, the remove() methods should throw java.lang.UnsupportedOperationException

as with the examples in the book.

Your iterators are required to be e  cient. That is, you may not do a full traversal of the tree when initializing the iterator, in order to determine the node order in advance. In addition, you may not restart the traversal every time the next() method is called (each iterator is required to store where it left o ). This means that the depth- rst traversals will need to use a stack to simulate recursion, and the level-order traversal should use a queue. Furthermore, you do not need to implement an inorder iterator.  Instead,

getInorderIterator() should throw a java.lang.UnsupportedOperationException. In addition, in-

clude in the comments for this method a short explanation of why TernaryTree does not support inorder traversal.

The nal interface, TernaryTreeBonus, declares two additional abstract methods that you may implement in your TernaryTree class for up to 8 bonus points. If you choose to complete this extra credit, your TernaryTree class should implement the TernaryTreeBonus interface (a subinterface of TernaryTreeInterface). You must also include a le named Bonus.txt in the root of your Box folder whose contents state that you completed the extra credit.

In addition to the methods required by the interfaces, your class must have the following constructors:

public TernaryTree(): initializes an empty tree

public TernaryTree(E rootData): initializes a tree whose root node contains rootData

2

public TernaryTree(E rootData, TernaryTree<E> leftTree, TernaryTree<E> middleTree,

TernaryTree<E> rightTree):  initializes a tree whose root node contains rootData and
whose subtrees are leftTree, middleTree, and rightTree, respectively.



Note: You are highly encouraged to write a test client that allows you to test the functionality of your implementation of TernaryTree prior to submission. You will be graded on each method’s functionality as it compares to the descriptions in the interfaces, so make sure you test each one to ensure it behaves as expected!



    • Grading

Your grade for this assignment will be based on each method’s functionality as it compares to the descriptions in both the interfaces and this document.



Note: Code that cannot be compiled and tested exactly as described will be given a grade of 0.




Method
Points

TernaryTree()

2
TernaryTree(E)
4
TernaryTree(E, tree, tree, tree)
6
getRootData()
2
isEmpty()
2
getHeight()
6
getNumberOfNodes()
6
getLevelOrderIterator()
16
getPreorderIterator()
18
getPostorderIterator()
20
getInorderIterator()
6

clear()
2
setTree(E)
4
setTree(E, tree, tree, tree)
6



4.1    Extra credit

In addition to the above methods from TernaryTreeInterface and its superinterfaces, you may also choose to make your TernaryTree implement TernaryTreeBonus. In this case, your TernaryTree class will need to override the two abstract methods in this bonus interface. If you choose to complete this extra credit, you must include a le named Bonus.txt in the root of your Box folder whose contents state that you completed the extra credit. If you fail to include this le, your grader will not know that you completed the bonus, and you will not receive the extra credit.




3

    • Submission

Upload your java les in the provided Box directory as additions to the provided code. All programs will be tested on the command line, so if you use an IDE to develop your

program, you must export the java les from the IDE and ensure that they compile and run on the command line. Do not submit the IDE’s project les. Your TA should be able to download your cs445-a5-abc123 directory from Box, and compile and test your code. Speci cally, javac cs445/a5/TernaryTree.java must compile your program, when executed from the root of your cs445-a5-abc123 directory.

In addition to your code, you may wish to include a README.txt le that describes features of your program that are not working as expected, to assist the TA in grading the portions that do work as expected. This le should be uploaded into the root of your cs445-a5-abc123 directory, not in the package directory.

Your project is due at 11:59 PM on Monday, December 9. You should upload your progress frequently, even far in advance of this deadline: No late submissions will be accepted.









































4