Counting Nodes and Counting Leaves

The program BinaryTreeDemo already has a method for inserting an item into a binary sort tree. That method is used in the main() routine to build three different BSTs. The root of each tree is then passed to a method named treeDemo, which is supposed to do several things with the tree. Currently, it calls a method bstPrint that prints the contents of the tree in alphabetical order using a recursive in-order traversal. The other operations, however, are not implemented. Your job is to implement them. The first thing that the program says about the tree is:

In this tree:
     The number of leaves in the tree is:         
     The number of nodes in the left subtree is:  
     The number of nodes in the right subtree is: 

But no numbers are included in the output. You should write two recursive methods, one to count the number of nodes in a tree and one to count the number of leaves in a tree. (Remember that a leaf is a node where both subtrees of the node are empty.) Call your methods to compute the required numbers and add them to the output.

Note that the two smaller trees are created by the main() routine by inserting a known sequence of words into an empty tree. You can figure out the exact form of those two trees and use it to check that the methods that you write for the lab are correct. The big tree, with 31 nodes, is created at random more for fun than anything else. But you can also examine the output of several runs to get an idea how "balanced" a random tree is likely to be.

Counting Letters

The program then wants to output the number of times each of the vowels occur in the tree:

The number of a's in the tree is:  
The number of e's in the tree is:  
The number of i's in the tree is:  
The number of o's in the tree is:  
The number of u's in the tree is:  

The number for a given letter should be obtained by counting all of the occurrences of that letter in all of the strings in the tree. Write another recursive method to do the counting, and use it to add the numbers to the output. The method will need a parameter to specify which letter is being counted, in addition to the parameter for the root of the tree.

Post-order Traversal

Next, you should write a method to do a recursive post-order traversal of the tree and call the method in the appropriate place in the treeDemo() method. The method is a trivial modification of the bstPrint method, which is already written. You should be able to do this part of the lab with a little copy-and-paste in not much more than a minute.

About the Generic Stack and Queue Classes

We have been writing classes such as StackOfInt and QueueOfString to implement data structures that hold just one kind of data. It seems silly to have to write a new class for each type of data that we might want to store in a stack or queue. It would be nice to have "parameterized" classes similar to ArrayList<T>, which can be used to create lists of any kind of object.

In fact, it's possible to write new parameterized classes. I have provided generic Stack and Queue classes for use in this lab, in the files Stack.java and Queue.java. (This is a preview of Chapter 10.) For example, you could make a queue of String by saying

Queue<String> que = new Queue<String>();

But what you will need for the next part of the lab is a stack of TreeNode and a queue of TreeNode.

Tree Traversal with Stack and Queue

For the final parts of the lab, you should write two non-recursive tree-traversal methods. One should use a stack to traverse the tree, and one should use a queue. Call the methods in the appropriate places in treeDemo().

The natural ordering when using a queue to do the traversal is breadth-first (also called level order). When using a stack, it's easiest to output the items in pre-order order, which is what you are asked to do. (Post-order and in-order using a stack are possible, but they require a few changes to the basic algorithm.) Just be careful that you do a left-to-right pre-order traversal, not a right-to-left pre-order traversal!