Question
For this computer assignment, implement a derived class to represent a binary search tree. Since a binary search tree is also a binary tree, implement
For this computer assignment, implement a derived class to represent a binary search tree. Since a binary search tree is also a binary tree, implement your binary search tree class from the base class of binary trees.
You are required to implement the binary search tree class in assignment6.cc file. You will need assignment6.h and assignment6main.cc, which are fully implemented. assignment6.cc already contains necessary headers
The definition of the derived binary search tree class is given here to facilitate the following description:
class BST : public binTree {
public:
BST() : binTree() {} // constructor
void insert( int ); // insert an item in the tree
bool search( int ); // search an item in the tree
bool remove( int ); // remove an item in the tree
// returns true when successful
int sumLeftLeaves(); // return the sum of values
// of left leaves private:
void insert( Node*&, int ); // private version of insert(int)
bool search( Node*&, int ); // private version of search(int)
bool remove( Node*&, int ); // private version of remove(int)
int sumLeftLeaves( Node*& n); // private version of sumLeftLeaves
};
The above public functions simply call their private versions. The private versions of insert (), remove (), search() and sumLeftLeaves () functions can be implemented as recursive functions. You can assume there are no identical numbers to be inserted into the tree.
When you implement the remove() function, consider three possible cases: the node to be removed (1) is a leaf; (2) has only one child; and (3) has two children. In the first case, simply delete the node. In the second case, bypass the node making a new link from its parent to its child, and delete the node. In the third case, find the immediate predecessor of the node first move to the left child of the node, and then move to rightmost node in the sub-tree, replace the value of the node with its immediate predecessor, and delete the predecessor. The pseudo-code is shown below.
BinarySearchTree-Remove ( Node n, int x)
1 if n is empty
2 stop 3 if ns data is greater than x
4 recursive call to BinarySearchTree-Remove ( ns left link, x) Binary Search Tree Class 2
5 if ns data is less than x
6 recursive call to BinarySearchTree-Remove ( ns right link, x)
7 if n has two non-empty children 8 pred <--find ns immediate predecessor
9 copy preds data to n
10 recursive call to BinarySearchTree-Remove( ns left link, preds data)
11 else if n is leaf
12 delete n
13 n <-- null
14 else // n has one child
15 temp <-- n
16 n <--ns only child
17 delete temp
*********************************
assignmnet6.cc file
#include #include "assignment5.h" #include "assignment6.h" using namespace std;
**********************
assignment5.h
#ifndef ASSIGNMENT5 #define ASSIGNMENT5
class binTree; class BST;
class Node { };
class binTree { public: binTree(); virtual void insert( int ); int height() const; unsigned size() const; void inorder( void(*)(int) ); void preorder( void(*)(int) ); void postorder( void(*)(int) );
protected: Node* root;
private: void insert( Node*&, int ); int height( Node* ) const; unsigned size( Node* ) const; void inorder( Node*, void(*)(int) ); void preorder( Node*, void(*)(int) ); void postorder( Node*, void(*)(int) ); };
#endif
*******************************
assignment6main.cc
#include #include #include #include #include "assignment5.h" #include "assignment6.h" using namespace std;
static const int MAX_COUNT = 20; static int mcount = 0;
void display2(int d) { if ( mcount < MAX_COUNT ) { cout << setw(4) << d; mcount++; } }
// produce a random number within range [1 1000] int rand_1000() { return rand() % 1000 + 1; }
void show_tree_information( BST& bst ) { cout << "Size of the tree: " << bst.size() << endl; cout << "Height of the tree: " << bst.height() << endl; cout << "In order traverse (displaying first " << MAX_COUNT << " numbers): " << endl; mcount = 0; bst.inorder( display2 ); cout << " Pre order traverse (displaying first " << MAX_COUNT << " numbers): " << endl; mcount = 0; bst.preorder( display2 ); cout << " Post order traverse (displaying first " << MAX_COUNT << " numbers): " << endl; mcount = 0; bst.postorder( display2 ); }
// For each value in searchVec, search it in the binary search tree // and report the number of successful searches void run_search( BST& bst, vector& searchVec ) { int success = 0; vector::iterator it; for ( it = searchVec.begin(); it != searchVec.end(); it++ ) if ( bst.search( *it ) ) success++; cout << endl << endl << "Out of " << searchVec.size() << " searches, " << success << " are successful." << endl << endl; }
int main() { //-------------- Create a B.S.T. using unique random numbers ----------- vector inputVec(1000); srand(7); generate(inputVec.begin(), inputVec.end(), rand_1000); sort(inputVec.begin(), inputVec.end()); vector::iterator it = unique(inputVec.begin(), inputVec.end()); inputVec.resize( it - inputVec.begin() ); random_shuffle( inputVec.begin(), inputVec.end() );
BST bst; for (it=inputVec.begin(); it!=inputVec.end(); it++)
bst.insert( *it ); cout << "A binary search tree is generated with random numbers: " << endl; show_tree_information( bst );
//-------------- Create a vector of random integers to be searched ------ vector searchVec(500); srand(11); generate( searchVec.begin(), searchVec.end(), rand_1000 );
cout << endl << endl << "Sum of left leaves: " << bst.sumLeftLeaves() << endl;
//------------ test search operations ---------------- run_search( bst, searchVec );
//------------ remove half of nodes from the tree --------- int counter = 0; random_shuffle( inputVec.begin(), inputVec.end() ); for ( it = inputVec.begin(); it < inputVec.end(); it += 2 ) { if ( bst.remove( *it ) ) counter++; } cout << endl << counter << " nodes are removed." << endl << endl;
show_tree_information( bst );
cout << endl << endl << "Sum of left leaves: " << bst.sumLeftLeaves() << endl;
//-------------- test search operations again --------------- run_search( bst, searchVec );
return 0; }
*****************************************
assignment6.h
#ifndef ASSIGNMENT6 #define ASSIGNMENT6 #include "assignment5.h"
class BST : public binTree { public: BST() : binTree() {} void insert( int ); bool search( int ); bool remove( int ); int sumLeftLeaves(); private: void insert( Node*&, int ); bool search( Node*&, int ); bool remove( Node*&, int ); int sumLeftLeaves(Node*&); };
#endif
**************************
assignemnt6 output : this is how the output is suppose to look like
**************
A binary search tree is generated with random numbers: Size of the tree: 635 Height of the tree: 19 In order traverse (displaying first 20 numbers): 2 4 5 6 7 8 10 11 13 15 16 17 18 19 20 23 25 26 27 31
Pre order traverse (displaying first 20 numbers): 422 420 72 23 2 5 4 7 6 20 15 13 8 10 11 19 17 16 18 63
Post order traverse (displaying first 20 numbers): 4 6 11 10 8 13 16 18 17 19 15 20 7 5 2 26 27 32 31 35
Sum of left leaves: 57692
Out of 500 searches, 321 are successful.
318 nodes are removed.
Size of the tree: 317 Height of the tree: 16 In order traverse (displaying first 20 numbers): 4 5 10 16 17 19 23 26 27 34 35 36 37 38 39 41 42 48 49 50
Pre order traverse (displaying first 20 numbers): 422 420 66 23 5 4 10 19 17 16 63 48 37 34 27 26 36 35 38 39
Post order traverse (displaying first 20 numbers): 4 16 17 19 10 5 26 27 35 36 34 41 42 39 38 37 49 55 50 48
Sum of left leaves: 23919
Out of 500 searches, 166 are successful.
****************
please do not change the name of the files
write in the comments if you have any questions
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started