Description

5/5 - (2 votes)

For this lab you are to work in teams of two with the following rules:

  • The two of you will sit together and use one computer.
  • You will both enroll yourself into the same team on Blackboard.
  • Each person must be typing on the keyboard for approximately 50% of the time – the easiest way to do this is to have one person be the typist for the first part and then have the other person be the typist for the second part.
  • If you complete this lab on your own or not in the presence of a lab instructor there will be an automatic 20% deduction in your grade.

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/labs/lab14 or in Blackboard.

In the same directory, or on Blackboard, 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 and is printed on the reverse side of this lab paper. The output for the function should just say: “Your search name appears 5 times.” With the number being correct, of course.

CHANGE TYPISTS

Finally write a function that counts the number of names (not unique names) that 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:

  • If the name is less than or equal to the name in the current node add in the size of the right subtree.
  • Move to the left and repeat.
  • If the name in the current node is less than the search tree move to the right without counting anything.
  • 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.”