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