Please help me with implementing this binary search tree.

Here is the code provide with the homework.

dsexceptions.h

#ifndef DS_EXCEPTIONS_H #define DS_EXCEPTIONS_H

class UnderflowException { }; class IllegalArgumentException { }; class ArrayIndexOutOfBoundsException { }; class IteratorOutOfBoundsException { }; class IteratorMismatchException { }; class IteratorUninitializedException { };

#endif

BinarySearchTree.h

#ifndef BINARY_SEARCH_TREE_H #define BINARY_SEARCH_TREE_H

#include "dsexceptions.h" #include #include #include

using namespace std;

// BinarySearchTree class // // CONSTRUCTION: zero parameter // // ******************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{ nullptr } { }

/** * Copy constructor */ BinarySearchTree( const BinarySearchTree & rhs ) : root{ nullptr } { root = clone( rhs.root ); }

/** * Move constructor */ BinarySearchTree( BinarySearchTree && rhs ) : root{ rhs.root } { rhs.root = nullptr; } /** * Destructor for the tree */ ~BinarySearchTree( ) { makeEmpty( ); }

/** * Copy assignment */ BinarySearchTree & operator=( const BinarySearchTree & rhs ) { BinarySearchTree copy = rhs; std::swap( *this, copy ); return *this; } /** * Move assignment */ BinarySearchTree & operator=( BinarySearchTree && rhs ) { std::swap( root, rhs.root ); return *this; } /** * 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 == nullptr; }

/** * 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 ); } /** * Insert x into the tree; duplicates are ignored. */ void insert( Comparable && x ) { insert( std::move( x ), root ); } /** * Remove x from the tree. Nothing is done if x is not found. */ void remove( const Comparable & x ) { remove( x, root ); }

// public: /** * Return tree walks of three types as a vector of elements in the tree * 0 - preorder, 1 - inorder, 2 - postorder */ int treeWalk(int type, vector & t_walk){ if (root==NULL ){ cout

/** * Display the tree walks; * does not work well for high trees. */

void displayTreeWalk(int type, ostream & out = cout ){ if (type2) out t_walk; treeWalk(type, t_walk); for(int i=0; i

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

BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt ) : element{ theElement }, left{ lt }, right{ rt } { } BinaryNode( Comparable && theElement, BinaryNode *lt, BinaryNode *rt ) : element{ std::move( 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 == nullptr ) t = new BinaryNode{ x, nullptr, nullptr }; else if( x element ) insert( x, t->left ); else if( t->element right ); else ; // Duplicate; do nothing } /** * 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( Comparable && x, BinaryNode * & t ) { if( t == nullptr ) t = new BinaryNode{ std::move( x ), nullptr, nullptr }; else if( x element ) insert( std::move( 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 == nullptr ) return; // Item not found; do nothing if( x element ) remove( x, t->left ); else if( t->element right ); else if( t->left != nullptr && t->right != nullptr ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else { BinaryNode *oldNode = t; t = ( t->left != nullptr ) ? 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 == nullptr ) return nullptr; if( t->left == nullptr ) 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 != nullptr ) while( t->right != nullptr ) 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 == nullptr ) 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 != nullptr ) 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 != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; }

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

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

/** * Return tree walks of a subtree rooted at b_node of * three types as a vector of elements in the tree * 0 - preorder, 1 - inorder, 2 - postorder */ int treeWalk(BinaryNode *b_node, int type, vector & t_walk){ if (type2){ cout element); walk_done1 = treeWalk(b_node->left, type, t_walk); walk_done2 = treeWalk(b_node->right, type, t_walk); break; case 1: walk_done1 = treeWalk(b_node->left, type, t_walk); t_walk.push_back(b_node->element); walk_done2 = treeWalk(b_node->right, type, t_walk); break; case 2: walk_done1 = treeWalk(b_node->left, type, t_walk); walk_done2 = treeWalk(b_node->right, type, t_walk); t_walk.push_back(b_node->element); break; }

if (walk_done1 != 0 || walk_done2 != 0){ cout

};

#endif

Here is the cpp code

TestBinarySearchTree.cpp

#include #include "BinarySearchTree.h" using namespace std;

// Test program int main( ) { BinarySearchTree t; int NUMS = 400000; const int GAP = 3711; int i;

cout

for( i = GAP; i != 0; i = ( i + GAP ) % NUMS ) t.insert( i );

for( i = 1; i

if( NUMS

for( i = 2; i

for( i = 1; i

BinarySearchTree t2; t2 = t;

for( i = 2; i

for( i = 1; i

// The following code randomly builds a BST and // display all the three tree walks of the built tree. BinarySearchTree t3; int numNodes = 10; cout

return 0;

}

1. (50 pts) Basic Setup: Implement or adapt a BST class (preferred) or a package of data structures and functions that contains implementation of the following operations on BSTs: inorder/preorder/postorder walk, search, maximum, minimum, predecessor, successor, insert and delete You may implement those BST operations on your own or adapt any existing programs you can find that implement BSTs. n the latter case, you should indicate clearly where you obtain the source code and what significant modifications you made if any. You also need to include testing code to verify the correctness of your program. In particular, you should test all the operations on a randomly built BST. Attached is the source code for the BinarySearchTree class from the textbook that you can use I added several functions to output tree walks (treeWalk") as well as testing code for that. The attached program also includes code for randomly generate a BST For this project, each node in a BST should at least four fields: key called element in the provided code), p, left, and right, representing the key value, and parent, left, and right child nodes of the given node. In addition, key values of all nodes in a BST are assumed to be integers