How to do a level traversal?

Question

I am trying to do a linear order traversal on a binary tree, but the problem is getting the correct output. Basically, I created a queue and start by forcing root, and then until the queue is empty. I will deactivate the first element and add its children to the end of the queue. When dropped, the common element () is returned. I had a problem converting this element to a node tree so that I could put my children at the end of the queue in the next step. Here is what I have done so far:

public void levelOrderTraversal() { NodeQueue<E> queue = new NodeQueue<E>(); BTPosition<E> current = root; queue.enqueue(current.element()); E temp = null; while(!queue.isEmpty()) { temp = queue.dequeue(); System.out.println(temp.toString()); current.setElement(temp); if (hasLeft(current)) { queue.enqueue(left(current).element()); } if (hasRight(current)) { queue.enqueue(right(current).element()); } } } 

The APIs for BTPosition and NodeQueue can be found at http://net3.datastructures.net/doc4/index.html?net/datastructures/

Any suggestions really appreciated.

Answer 1

You want the queue to be of type BTPosition<E> . <E> is simply an object type, such as Integer or String . BTPosition seems to be the actual node in your binary tree.

 public void levelOrderTraversal() { NodeQueue<BTPosition<E>> queue = new NodeQueue<BTPosition<E>>(); BTPosition<E> current = root; queue.enqueue(current); while(!queue.isEmpty()) { current = queue.dequeue(); System.out.println(temp.element().toString()); if (current.getLeft() != null) { queue.enqueue(current.getLeft()); } if (current.getRight() != null) { queue.enqueue(current.getRight()); } } }