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

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
Suppose the file btree.in contains this:
C E @ B F @ @ @ G A @ @ N J @ @ @
Program P8.4 will build the tree shown at the start of this section and print the following:
The level-order traversal is: C E G B A N F J
8.10 Some Useful Binary Tree Functions
We now show you how to write some functions (in the class BinaryTree ) that return information about a binary tree.
The first counts the number of nodes in a tree:
public int numNodes() {
return countNodes(root);
}
private int countNodes(TreeNode root) {
if (root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
If bt is a binary tree, bt.numNodes() will return the number of nodes in the tree. Counting the nodes is delegated
to the private function countNodes .
The next function returns the number of leaves in the tree:
public int numLeaves() {
return countLeaves(root);
}