Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 241

To perform a level-order traversal, we will need to use a queue. The following algorithm shows how:

add the root to the queue, Q
while (Q is not empty) {
remove item at the head of Q and store in p
visit p
if (left(p) is not null) add left(p) to Q
if (right(p) is not null) add right(p) to Q
}

For the previous tree, the following occurs:

• Put

C on Q .

•

Q is not empty, so remove and visit C ; add E and G to Q , which now has E G .

•

Q is not empty, so remove and visit E ; add B to Q , which now has G B .

•

Q is not empty; remove and visit G ; add A and N to Q , which now has B A N .

•

Q is not empty; remove and visit B ; add F to Q , which now has A N F .

•

Q is not empty; remove and visit A ; add nothing to Q , which now has N F .

•

Q is not empty; remove and visit N ; add J to Q , which now has F J .

•

Q is not empty; remove and visit F ; add nothing to Q , which now has J .

•

Q is not empty; remove and visit J ; add nothing to Q , which is now empty.

Q is empty; the traversal ends having visited the nodes in the order C E G B A N F J .
We will need the following to perform the queue operations. First, we define the class QueueData as follows:

•

public class QueueData {
TreeNode node;

public QueueData(TreeNode n) {
node = n;
}
} //end class QueueData

Next, we define the class QNode :

public class QNode {
QueueData data;
QNode next;

public QNode(QueueData d) {
data = d;
next = null;
}
} //end class QNode