Project 3 - Trees

Due - Tuesday, December 20, 2005

The goal of this project is to give you experience with Binary Search Trees.

For this project, you will implement a Binary Search Tree that will be used as the data structure for a telephone number database. Your program will begin by reading from a file several records that will be inserted into the tree. Each record should contain, at minimum, the name and phone number for a particular person. The tree should be ordered by name.

Once the initial tree is built, your program will read, from a separate file, and execute several delete and find operations. The result of each find should be stored in a separate linked list. When all operations are completed, your program should output three files. The first file will contain an alphabetized list of names and numbers. The second file will contain the result of a pre-order traversal of the tree. The third file will contain the results of the find operations.

You should begin with the base BST and TreeNode classes that you completed for your final homework assignment. Your final BST class must support, at minimum, the following functions:

insert(record) - The insert function takes as input a name and telephone number, either as separate items or as a single object. The function will insert a TreeNode containing the information at the appropriate position in the tree. The tree should be ordered by name.

find(string) - The find function takes as input a string and determines whether the tree contains a node containing a name that matches the string specified as input. The function should return a reference to the node if found and NULL if not found.

delete(string) - The delete function takes as input a string and will remove from the tree any node that contains a name that matches the string specified as input.

The file used to build the tree will be of the form:
name number
name number
name number
The file specifying the series of operations to be performed will contain 0 or more lines. Each line will start with either delete or find and will be followed by a space and a name. An example would look as follows:
delete Marx
find Markus
delete Markus
find Romano
As a complete example, if the build file looked as follows:
Alexander 555-1213
Adams 555-9876
Romano 555-4536
Vega 555-0983
Jensen 555-8776
Marx 555-9433
Your tree would look as follows, where each node also contains the phone number specified:
Alexander
(left child - Adams)
(right child - Romano)
Romano
(left child - Jensen)
(right child - Vega)
Jensen
(right child - Marx)

After performing the example operations outlined above, your tree would look as follows:
Alexander
(left child - Adams)
(right child - Romano)
Romano
(left child - Jensen)
(right child - Vega)
Jensen

In addition, your linked list of find operations would contain two records. The first record would indicate a failure to find Markus and the second record would store the name and number of Romano.

Implementation Hints

  1. Make sure to account for all error conditions. For example, handle the case when your input file(s) are empty and the case when a find or delete specifies a name that does not exist in the tree.
  2. You will need to figure out how to do file input/ouput in C++. There are several online resources that you may find helpful. Look around on your own, and come to me when you have questions. Getting you to look for these resources on your own is part of the project!

Extra Credit Opportunity

For extra credit, modify your Binary Search Tree to support a change operation. This operation will allow you to change the name stored in a particular node from its old value to a new value. This operation will require as input the old name and the new name. Remember, the tree must remain ordered. This means that the node with the updated name may need to be moved to a different location in the tree.

Turn in Procedure

  1. Complete and submit your working code via email.
  2. Make sure that each function is well documented. Your documentation should specify the type and function of the input paramaters and ouput.
  3. Run your program on a variety of inputs ensuring that all error conditions are handled correctly.
Reminder: No part of your code may be copied from any other source. All code submitted must be original code written by you.
Sami Rollins