CS 14: Programming Assignment 7

Directory to turnin: as7

Due date: Wednesday Dec 6, 2000

Synopsis:

In this assignment, you will implement a binary search tree that holds any type of value and uses a string key.

Note that this program must be compiled and executed under Linux.

Details:

The binary search tree you coded in lab 9 is limited in that it can only hold integer values. In many cases, you may need to store many kinds of information and may want to use a string key instead of an integer.

For this assignment, you should create a binary search tree in which each node contains a separate data member for the key and the data being stored. The key should be a string (i.e. char *) and the data should be a pointer to anything (i.e. void *).

Following are the methods your class will need:

insert
The insert method should take 2 parameters, a string and a void * pointer. (It's prototype would be bool insert( char *key, void *data ); It should create a node, save the key and data, and insert the node into the tree. Note: Use the char *strdup( char * ) function when saving the key so that a new char * array is dynamically allocated. Because there is no way to know the size of the data, it can not be duplicated, so it can just be assigned to your data member.

The method should make sure neither parameter are NULL; if either are, it should do nothing but return false (to indicate an error). Also, if allocating a new node fails, false should be returned.

To compare two string keys, use the int strcmp( char *str1, char *str2 ) function. It returns a value < 0 if str1 is less than str2, a value > 0 if str1 is greater than str2, or 0 if the strings are equal.

The method should return true if the new node is created and inserted into the tree successfully.

remove
The remove method should take a string parameter for the key and return a void *.

The method should search the tree for a node with a key that matches the passed in value. If it finds a match, it should remove the node and return the data from the removed node. If no match is found, the method should return NULL.

search
The search method must also be modified to take a string parameter and return a void * variable. It should search the tree for a node with a key that matches the passed in value and return the data from the matching node, if found. If no match is found, the method should return NULL.
minValue
The minValue method should return a void * variable. It finds and returns the data from the node with the smallest key value, or NULL if the tree is empty.
maxValue()
The maxValue method should return a void * variable. It finds and returns the data from the node with the largest key value, or NULL if the tree is empty.
isEmpty
The isEmpty method should return true if the tree is empty or false if it is not.
dumpSorted
The dumpSorted method should print all the keys in the tree, in order (i.e. you will need to do an inorder tree walk). The method takes no parameters and has no return value.

main.cpp:

This file should contain your main function. It should declare a binary search tree variable and use it to perform operations.

Note that the binary search tree will not and can not know what type of data you are inserting into it. All it knows is that the keys are strings and the data is a pointer to a void *. Therefore, your program must keep track of this and do the proper typecasts. Have your main program use integers as the data being inserted into the tree.

Following is sample code showing how an integer value can be added and removed from a tree:

   int *data = new int;
   *data = 10;

   BST.insert( "integer_data", (void *) data );

   int *removed_data = (int *) BST.remove( "integer_data" );
   if ( removed_data == NULL )
      cout << "Tree was empty\n";
   else
      cout << "Removed " << *removed_data << " from the tree\n";
Your main program, however, should provide a menu of options to the user, allowing him/her to insert, remove, etc. Note that when inserting an integer, you will have to ask the user to enter in two pieces of information: the key value (a string) and the data (an integer). Be sure to dynamically allocate the integer that is passed to the insert method.

Compiling and Running the Program

The program should be compiled and executed under Linux. The graders will not attempt to compile using Visual C++.

Note: In past assignments, some students have included .cpp (or .cc) files within other .cpp( or .cc) files. Do not do this. Only header (.h) files should be included in a file.

Include a makefile to compile your program.