Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Please help me with implementing this binary search tree in C++. The following is the code provided with the assignment. When I try to compile
Please help me with implementing this binary search tree in C++. The following is the code provided with the assignment. When I try to compile it I get the following error:
fatal error: dsexceptions.h: No such file or directory compilation terminated.
Thank you in advance!
---------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// 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 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
---------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 t2; t2 = t; for( i = 2; i The Binary Search Tree Class In this assignment, you are to use the binary search tree (BST) from class, the code is the file BinarySearchTree.h (available on the anouncement page) and should be copied into your main program. BST Sort Now implement the BST sort described below: 1. Initialization The user inputs n. Then n random numbers between 1 and I are are inserted into a BST 2. Loop Write the numbers 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 nachine bobby for n The command is 50000, 150000, 500000. time ./a.out > /devull Explanation: In order to measure run time the output must be redirected the to /devull (or else your screen will fill up with thousands of numbers.) To measure user run time you use the command time command, which is described in greater detail on the announcement page
Step by Step Solution
There are 3 Steps involved in it
Step: 1
![blur-text-image](https://dsd5zvtm8ll6.cloudfront.net/includes/images/document_product_info/blur-text-image.webp)
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
![blur-text-image](https://dsd5zvtm8ll6.cloudfront.net/includes/images/document_product_info/blur-subtext-image.webp)
Step: 3
![blur-text-image](https://dsd5zvtm8ll6.cloudfront.net/includes/images/document_product_info/blur-subtext-image.webp)
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started