CS 14 - Lab 9

In this lab you are going to create a BST (binary search tree) class that holds integer values. See Chapter 13 for details on the algorithms needed for this class.

Note that the program must be written, compiled, and executed under Linux.

The Class

Define a class BST that contains the following public methods:

BST(); (constructor)
~BST(); (destructor)
bool isEmpty();
bool insert( int value );
bool search( int value );
int minValue();
int maxValue();

Details

BST()

The constructor should initialize any variables that need to be initialized.

~BST()

The destructor should delete any dynamic data allocated by the class (i.e. the tree nodes created when inserting). To do this properly, use a post-order tree walk to ensure that a node's children are deleted before the node itself.

bool isEmpty()

This method returns true if the tree is empty, false otherwise.

bool insert( int value );

This method inserts the value passed into the tree. If there is an error (i.e. creating a tree node fails), the method should return false. If the value is inserted, the method should return true.

bool search( int value );

This method should search for the value passed in the tree. If the value is found, the method should return true, else it should return false.

int minValue();

This method should return the smallest value in the tree or 0 if the tree is empty.

int maxValue();

This method should return the largest value in the tree or 0 if the tree is empty.

Main Program

Create a main program that creates a BST object, then presents a menu of options to the user. The user should be able to insert values, search for a value, and find the minimum and maximum values. For the latter, if the tree is empty (use the isEmpty method), inform the user of this, otherwise call the minValue or maxValue method.

Compiling With a Makefile

Copy the makefile you created in lab 6 and modify it to compile this lab assignment.

Grading

When you have finished the program, your TA will grade it. To receive full credit, your TA will check all of the following:

You created a binary search tree class (BST) that works correctly
You have a makefile to compile your program
The program is properly commented. Each function should have a comment at the beginning explaining what it does, what each of its parameters are for, and the return value (if any). In addition, the code within each function should have comments as appropriate to explain how it works.
The program is well formatted (i.e. style). For example, you should be consistent with your indenting in the program.