Description
Using this struct that we have been working with in class:
struct Bnode{
string data;
Bnode * left;
Bnode * right;
};
Create a little program that is able to build a binary search tree from the names listed in the file, names.txt, which is available in ~jdolan/cs2401/hw/hw7
In the same directory you will find a source file containing some functions and definitions that are very useful for this lab. They appear in the file btreelab.cc.
You can use the inorder traversal that I have given you to see that the names are in there.
Now write a function that searches for and counts the number of times that a particular name occurs. Let the user input the name from the keyboard. (A description of the algorithm for this appears in your book on p. 523 in the 4th edition and p. 518 in the 3rd edition.) The output for the function should just say: “Your search name appears 5 times.” With the number being correct, of course.
Finally write a function that counts the number of names (not unique names) that are in the tree and greater than (i.e. come after in the alphabet) the search name. This later function will work better if it is done recursively. Think of it like this:
o If the name is less than or equal to the name in the current node add in the size of the right subtree.
o Move to the left and repeat.
o If the name in the current node is less than the search tree move to the right without counting anything.
o The base case is when you hit NULL, a condition that will return a 0.
Submit a copy of your source code, along with a script that looks for the names “Matthew” and “Jessica.” The script should show the operation of both of your functions for these names. (i.e. The number of times each of these names appears and the number of names in the tree that are greater than these names. This can be done with a single running of the program or with two runnings of the program.)
