HW5 : Level-order Traversal

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.

Selection_031

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.