Java Reference
In-Depth Information
And, finally, here's the class Queue :
public class Queue {
QNode head = null, tail = null;
public boolean empty() {
return head == null;
}
public void enqueue(QueueData nd) {
QNode p = new QNode(nd);
if (this.empty()) {
head = p;
tail = p;
}
else {
tail.next = p;
tail = p;
}
} //end enqueue
public QueueData dequeue() {
if (this.empty()) {
System.out.printf("\nAttempt to remove from an empty queue\n");
System.exit(1);
}
QueueData hold = head.data;
head = head.next;
if (head == null) tail = null;
return hold;
} //end dequeue
} //end class Queue
Note that if you put QueueData in the same file as Queue or the program that uses Queue , you must omit the word
public . Similar remarks apply to the class QNode .
Using Queue and QueueData , we can write the instance method levelOrderTraversal in BinaryTree as follows:
public void levelOrderTraversal() {
Queue Q = new Queue();
Q.enqueue(new QueueData(root));
while (!Q.empty()) {
QueueData temp = Q.dequeue();
temp.node.data.visit();
if (temp.node.left != null) Q.enqueue(new QueueData(temp.node.left));
if (temp.node.right != null) Q.enqueue(new QueueData(temp.node.right));
}
} //end levelOrderTraversal
Putting it all together, we write Program P8.4, which builds a tree using data from the file, btree.in , and performs
a level-order traversal. Note that, in order to put the entire program in one file, only the class containing main is
declared public . In the other classes, only the methods relevant to this problem are shown.
Search WWH ::




Custom Search