Lab 1--Build a Binary Search Tree

Due date: This is a part in-lab and part out-lab type lab. The full lab will be due at the beginning of lab, July 5th.

Purpose

programming a tree from scratch

What to do

Design and implement a class for the node in your tree.
Use the excerpts of code from the book as a reference.
Design a class for the tree itself. One data member (or attribute) in this class should be a reference variable to point to the root.
Decide on the functionality you will need. You must implement insertion, deletion, search, and outputting the tree's contents in-order, pre-order and post-order.
Write a driver to call your methods.
First have the tree hold an object that has an integer that can be compared until everything is working, then modify your tree to handle objects that can be compared. So first just compare the ints in the Node, then modify the code to compare the whole Node as a comparable object.
- Remember that your key must be Comparable. Any methods in your tree class that say what the data type of the key is should be Comparable, not Object. This lets you use the compareTo method in the tree class.
At the end of today's lab I would like to see you inserting elements into the tree, deleting properly and at least one output of the contents. Get as much done as you can.

Grading Criteria

You will be graded on the following: