Homework #5 -- Starting a BST class

Assigned: Mon, 2/26

Due: At the beginning of class, Wed, 3/7

Worth: 40 pts.

Objective: To get some practice with C++ and to make sure you truly understand BST algorithms

Collaboration: You are welcome to work together on this, but each person should do the actual coding individually.

Note: A lot of this code is in your book. Yes, I know that. Yes, you are welcome to use it, although the BST class we are writing is not templated and is structured somewhat differently. For your own good, please make sure you understand what you are writing.

Directions:

1. A copy of bst.h and bstdrv.cpp are in ~vanbusum/public Feel free to copy them to your own directory.

2. Add the following functions:

preorder (5 pts)

//prints the nodes of the tree doing a preorder traversal

postorder (5 pts)

//prints the nodes of the tree doing a postorder traversal

find (10 pts)

//returns a pointer to the node containing element n

//if n is not found, returns NULL

makeEmpty (8 pts)

//recursively deletes all of the nodes in the tree

isEmpty (5 pts)

//returns 1 (True) if the tree is empty

//else returns 0 (False)

delete (7 pts)

//deletes node n from the tree

What to turn in:

Turn in a printout of bst.h. You do not need to turn in your driver. I will not explicitly be grading on style, but I do expect well commented, clean code that I can understand easily.

Also, create a subdirectory called BST in your comp121/submissions directory in your UNIX account. Put a copy of bst.h into this subdirectory. I will run your bst.h code with my own driver to test all of the above operations.