I need help implementing a C++ Binary Search Tree Sort,using these instructions.

using this header:

#ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H

#include "dsexceptions.h" #include // For NULL using namespace std;

// BinarySearchTree class // // CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x // bool contains( x ) --> Return true if x is present // 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( ) --> Print tree in sorted order // ******************ERRORS******************************** // Throws UnderflowException as warranted

template class BinarySearchTree { public: BinarySearchTree( ) :root( NULL ) { }

BinarySearchTree( const BinarySearchTree & rhs ) : root( NULL ) { *this = rhs; }

/** * Destructor for the tree */ ~BinarySearchTree( ) { makeEmpty( ); }

/** * Find the smallest item in the tree. * Throw UnderflowException if empty. */ const Comparable & findMin( ) const { if( isEmpty( ) ) throw UnderflowException( ); return findMin( root )->element; }

/** * Find the largest item in the tree. * Throw UnderflowException if empty. */ const Comparable & findMax( ) const { if( isEmpty( ) ) throw UnderflowException( ); return findMax( root )->element; }

/** * Returns true if x is found in the tree. */ bool contains( const Comparable & x ) const { return contains( x, root ); }

/** * Test if the tree is logically empty. * Return true if empty, false otherwise. */ bool isEmpty( ) const { return root == NULL; }

/** * Print the tree contents in sorted order. */ void printTree( ostream & out = cout ) const { if( isEmpty( ) ) out

/** * Make the tree logically empty. */ void makeEmpty( ) { makeEmpty( root ); }

/** * Insert x into the tree; duplicates are ignored. */ void insert( const Comparable & x ) { insert( x, root ); } /** * Remove x from the tree. Nothing is done if x is not found. */ void remove( const Comparable & x ) { remove( x, root ); }

/** * Deep copy. */ const BinarySearchTree & operator=( const BinarySearchTree & rhs ) { if( this != &rhs ) { makeEmpty( ); root = clone( rhs.root ); } return *this; }

private: struct BinaryNode { Comparable element; BinaryNode *left; BinaryNode *right;

BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt ) : element( theElement ), left( lt ), right( rt ) { } };

BinaryNode *root;

/** * Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the subtree. * Set the new root of the subtree. */ void insert( const Comparable & x, BinaryNode * & t ) { if( t == NULL ) t = new BinaryNode( x, NULL, NULL ); else if( x element ) insert( x, t->left ); else if( t->element right ); else ; // Duplicate; do nothing }

/** * Internal method to remove from a subtree. * x is the item to remove. * t is the node that roots the subtree. * Set the new root of the subtree. */ void remove( const Comparable & x, BinaryNode * & t ) { if( t == NULL ) return; // Item not found; do nothing if( x element ) remove( x, t->left ); else if( t->element right ); else if( t->left != NULL && t->right != NULL ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else { BinaryNode *oldNode = t; t = ( t->left != NULL ) ? t->left : t->right; delete oldNode; } }

/** * Internal method to find the smallest item in a subtree t. * Return node containing the smallest item. */ BinaryNode * findMin( BinaryNode *t ) const { if( t == NULL ) return NULL; if( t->left == NULL ) return t; return findMin( t->left ); }

/** * Internal method to find the largest item in a subtree t. * Return node containing the largest item. */ BinaryNode * findMax( BinaryNode *t ) const { if( t != NULL ) while( t->right != NULL ) t = t->right; return t; }

/** * Internal method to test if an item is in a subtree. * x is item to search for. * t is the node that roots the subtree. */ bool contains( const Comparable & x, BinaryNode *t ) const { if( t == NULL ) return false; else if( x element ) return contains( x, t->left ); else if( t->element right ); else return true; // Match } /****** NONRECURSIVE VERSION************************* bool contains( const Comparable & x, BinaryNode *t ) const { while( t != NULL ) if( x element ) t = t->left; else if( t->element right; else return true; // Match

return false; // No match } *****************************************************/

/** * Internal method to make subtree empty. */ void makeEmpty( BinaryNode * & t ) { if( t != NULL ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = NULL; }

/** * Internal method to print a subtree rooted at t in sorted order. */ void printTree( BinaryNode *t, ostream & out ) const { if( t != NULL ) { printTree( t->left, out ); out element right, out ); } }

/** * Internal method to clone subtree. */ BinaryNode * clone( BinaryNode *t ) const { if( t == NULL ) return NULL; else return new BinaryNode( t->element, clone( t->left ), clone( t->right ) ); } };

#endif

BST Sort Now implement the BST sort described below 1. Initialization The user inputs n. Then n random numbers between 1 and 10000 are are inserted into a BST 2. Loop Write the umbers in sorted order to the screen. In order to do this you repeatedly find the minimum, write it to the screen and delete it until the list is empty. Run Time Experiments Tabulate the user run time on machine bobby for n 50000, 150000, 500000