Home | About | Calendar | Projects | Assignments | Classes | Resources
{Programming III }
     
 
PROJECT 2
 
REMINDERS
 
.Implementing Binary Search Trees in the MBCS.

Implementing a Binary Search Tree data structure in the Marine Biology Case Study is not easy. We will make our job easier by first writing the Binary Search Tree code, testing it, and then adding it to the Case Study. Our definition of class BinarySearchTree will start with the definition of a struct:

template <class Comparable>
struct BinaryNode
{

Comparable element;
BinaryNode *left;
BinaryNode *right;

BinaryNode( const Comparable & theElement,
            BinaryNode *lt = 0, BinaryNode *rt = 0)
     : element( theElement ),
      left( lt ),
      right( rt )
{}
// Note. We could have made struct BinaryNode a class and then
// identified this class as a friend to BinarySearchTree with the
// following line:
// friend class BinarySearchTree<Comparable>;

};

Your job is to implement class BinarySearchTree with the following member functions:

BinarySearchTree( const BinarySearchTree & rhs); // Copy constructor
~BinarySearchTree(); // Destructor
void insert( const Comparable & x ) // Insert x
void remove( const Comparable & x ) // Remove x
Comparable find( const Comparable & x ) // Return item that matches x
Comparable findMin( ) // Return smallest item
Comparable findMax( ) // Return largest item
boolean isEmpty( ) // Return true if empty; else false
void makeEmpty( ) // Remove all items
void printTree( ostream & out ) // Print tree in sorted order
const BinarySearchTree & operator=( const BinarySearchTree & rhs );

I cannot emphasize strongly enough how important it is going to be to implement this code in small steps. I would recommend writing insert and printTree first, since those will allow you to test the rest of the code.

I will work on getting this Binary Search Tree class to work within the case study, but you can work on it for the optional.

.Optional.

Get your new BinarySearchTree class to work in the case study.

.Scoring.

This program will be collected through the dropbox. Projects are a major component of your grade, and we will only have 3 or 4. Doing well on projects is a major factor in earning a good grade in the course.

.Resources.

[ The Marine Biology Case Study ]

   Implement the code in small steps.  Write one member function and test it thoroughly before moving on to the next one.
 
Page prepaed by Christian Day.
Site design by Kelly Moran
BackForward
 
 
Last Updated: