Project 4 - Trees

Due - Monday, December 20, 2004

The goal of this project is to give you experience with Binary Search Trees. For this project, you will implement a Binary Search Tree, build an instance of the Tree based on input from a file (e.g., build.txt), traverse a set of paths specified in a separate file (e.g, paths.txt), and print to a file the data stored in the nodes located by the paths. Your program must implement a TreeNode class (not structure) which stores information about the a particular node of the tree. You must also implement a Tree class that supports two main functions:

insert(string) - The insert function takes as input a string and inserts a TreeNode containing the string into the appropriate position in the tree. The tree must be maintained as an ordered tree.
followPath(char path[]) - The followPath function takes as input an array of characters representing the path to follow, follows the path specified, and returns the string found in the node located by the path.

The file used to build the tree will be of the form:
insert name
insert name
insert name
The file used to specify the paths will specify a series of moves -- left (L) or right (R). There will be several paths. You must read in each path, follow it, and then print to an output file and the name located by the path.

As an example, if the build file looked as follows:
insert Alexander
insert Adams
insert Romano
insert Vega
insert Jensen
insert Marx
Your tree would look like:
Alexander
(left child - Adams)
(right child - Romano)
Romano
(left child - Jensen)
(right child - Vega)
Jensen
(right child - Marx)

If your path file looked like:
L
RLR
Your output file would look like:
Adams
Marx

Implementation Hints

  1. Your paths file will contain an arbitrary number of paths. You should continue reading in and following paths until you hit the end of the file.
  2. The paths will be arbitrarily long. Some may be one hop and others may be several hops.
  3. A path may hit a leaf before the entire path has been traversed. In this case, you should indicate an error.
  4. 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 delete operation. Your build file should have both insert and delete operations and your program should insert or delete appropriately from the tree. Once you have built the tree, follow the paths specified in the paths file.

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. Copy and paste the output of your test runs to the bottom of your program. Make sure the output is a comment. That means, put a /* before the output and a */ after the output.
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