COSC 072/503 Project 4

COSC 072/503: Computer Science II

Project 4
Spring 2005

Due: Apr 22 @ 5 PM
10 points

This project involves implementing an ADT for a binary search tree.

Implement the TreeNode<T> class for nodes of a binary tree.
Use the TreeNode<T> class to implement either the BinarySearchTree<T> or the BST<T> class. Or, perhaps, if you prefer, implement BSTree<T>. In addition to a default constructor and a destructor, implement the methods empty, clear, preorder, postorder, inorder, find, insert, and load.
The purpose of the empty and clear methods should be obvious.
The preorder, postorder, and inorder methods should print the pre-order, post-order, and in-order traversals, respectively, to STDIN (i.e., cout). If I were you, I'd get these methods working on a hard-coded tree before attempting to implement the insert method, which is challenging. For example, I'd implement a method called ``build'' that builds a small binary search tree when called. Once you get one of these printing methods implemented, it will be easier to implement and debug the insert method.
The load method should take a filename (a string) as an argument and read the corresponding file containing some number of items. It should then use the insert method to insert the items into the tree. For this project, all of the items will be single characters. For example, if we have a file containing the characters,
```
d b f a c e g
```
the load method should build the following binary tree:

To test your BSTree class, the main function should read a filename from the command line. The file will contain commands that will drive your program, as follows:

Command Example Description
L filename L tree.dta Loads a tree from filename
I item I z Inserts item into the tree
F item F z Finds item in the tree and prints "found" to STDOUT if the item is in the tree; prints "not found" otherwise.
R R Prints the pre-order traversal of the tree to STDOUT
O O Prints the post-order traversal of the tree to STDOUT
N N Prints the in-order traversal of the tree to STDOUT
C C Clears the tree

Command	Example	Description
L filename	L tree.dta	Loads a tree from filename
I item	I z	Inserts item into the tree
F item	F z	Finds item in the tree and prints "found" to STDOUT if the item is in the tree; prints "not found" otherwise.
R	R	Prints the pre-order traversal of the tree to STDOUT
O	O	Prints the post-order traversal of the tree to STDOUT
N	N	Prints the in-order traversal of the tree to STDOUT
C	C	Clears the tree

As an example, if the file cmds.txt contains the following commands:

I b
I a
I c
R
F c
F z

the output of your program might be as follows:

% a.out cmds.txt
Inserting b...
Inserting a...
Inserting c...
Pre-order traversal: bac
Finding c...found
Finding z...not found

The main function should always create a BSTree of characters.

We will talk about reading command-line arguments in class, but the following main function illustrates how to read a string from the command line:

#include <iostream>
#include <string>

using namespace std;

int main( int argc, char *argv[] )
{
  if ( argc != 2 ) {
    cout << argv[0] << "  (e.g., '" << argv[0]
         << " tree.dta')" << endl;
    exit(0);
  } // if
  string filename( argv[1] );
  cout << "Filename: " << filename << endl;
  return 0;
} // main

EXTRA CREDIT: If you overload the assignment operator, operator=, I'll give you an extra 10%. It must make a deep copy of the tree.

Use stepwise refinement and incremental development. For example, implement and test the TreeNode<T> class before implementing the BSTree<T> class.

You must provide a working UNIX Makefile with your submission. The one from Project 3 should work with minor changes.

IMPORTANT: For this project, do not worry about documenting. At this point, you get it if you're going to.

Instructions for Electronic Submission:

Submit your project in the same way you submitted Project 3