Due: Thursday 7/3/14 @5:30pm via users.cs.umb.edu:cs210/hw5
Purpose: To gain experience implementing a level order traversal of a binary tree.
Study the following Level Order Traversal Algorithm so that you understand the design of the method that you will need to implement in this assignment.
Create a queue called nodes Create an unordered list called results Enqueue a reference to the root node onto the nodes queue While the nodes queue is not empty Dequeue the first element If it is not null add it to the rear of the results list Enqueue the children of the element on the nodes queue Else Add null to the rear of the results list Return an iterator for the results list
The following files are here: https://github.com/ieee8023/cs210-summer2014 or hw5
BinaryTreeADT.java : Interface for a binary tree.
BinaryTreeNode.java : Class used by LinkedBinaryTree for nodes of tree.
LinkedBinaryTree.java : Implements BinaryTreeADT interface.
LevelTraverse.java : Has a main method that builds a tree and iterates over it.
You need to design and add code to the levelOrderIterator method of the LinkedBinaryTree class where indicated.
1. Create a queue using the java.util.Queue interface and java.util.LinkedList class.
2. Create a linkedlist using the java.util.LinkedList class to contain the elements in level order.
3. Write code to implement the Level-order Traversal of the tree.
4. Write a memo.txt describing any problems you had during this assignment and what you learned.
A sample run of the finished program is shown here:
$ java LevelTraverse Root Child1 Child2 Grandchild1 Grandchild2 . . .
Grading (total 10 points):
Turn in the following files: BinaryTreeADT.java, BinaryTreeNode.java, LinkedBinaryTree.java, LevelTraverse.java, memo.txt
3 points: Queue correctly filled
5 points: Level order implemented correctly
2 points: memo.txt, easy to grade.