For this computer assignment, implement a derived class (as a template) 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, which you implemented in your previous assignment.

The definition of the derived class of a binary search tree (as a template) is given as follows:

template < class T >

class binSTree : public binTree < T > {

public:

void insert ( const T& x );

void remove ( const T& x );

private:

void insert ( Node < T >*&, const T& );

t void remove ( Node < T >*&, const T& );

Node < T >* pred ( Node < T >* );

Where x is the target value for insert ( ) and remove ( ) functions. These public functions simply call their private versions

The private versions of insert ( ) and remove ( ) functions can be implemented as recursive functions. 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 predecessor of the node first move to the left child of the node, and then move to rightmost node in the tree, replace the value of the node with the value of its predecessor, delete the predecessor, and update the link to the deleted node, where the private non-recursive member function pred ( ) can be used to return the predecessor of a node

To test your derived class, the source file of a driver program, prog7.cc, is supplied to you, which is in directory: ~cs340/progs/17f/p7. This program generates two sets of random integers in the range [ 0, R ] with R = 1000, and inserts these numbers of the first set in a vector of integers and the numbers of the second set in another vector of integers, and inserts the numbers of the first set in a binary search tree. The program searches for each number in the second vector in the binary search tree before and after the numbers in the second vector is removed from the tree. At the end, it prints the following values for the binary search tree: the number of nodes and the height of the tree. Finally, it prints the data values in the binary search tree in ascending order before and after the removals, since traversing a binary search tree inorder results a sorted list of values.

To get the size of a binary search tree, add the public and private versions of the size ( ) function in your binTree class with the prototypes unsigned size ( ) const and unsigned size ( Node < T >* ) const, respectively.

Put the implementation of your binary search tree class in a separate header file, say binSTree.h. Modified version of the class Node from the previous assignment includes the binTree and binSTree classes as friends, so the objects of these two classes can access the private members of the class Node. Include the header file Node.h in your header file binTree.h, and include the header file binTree.h in your header file binSTree.h. Make it sure that each header file is included only once, so the contents of each header file should be guarded as follows:

// include system header files

using namespace std;

#ifndef aconstvalue

#define aconstvalue

// statements in the header file

#endif .,

Driver program:

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

#define SEED1 1 // seed for 1st RNG #define SEED2 31 // seed for 2nd RNG

#define N1 50 // size of 1st vector #define N2 100 // size of 2nd vector #define R 1000 // high val for rand integer

#define LSIZE 20 // no of vals printed on line #define ITEM_W 4 // no of spaces for each item

unsigned sz; // size of tree

// class to generate rand ints class RND { private: int seed, high; public: RND ( const int& s = 1, const int& h = 1 ) : seed ( s ), high ( h ) { srand ( seed ); } int operator ( ) ( ) const { return rand ( ) % ( high + 1 ); } };

// prints out val passed as argument template < class T > void print ( const T& x ) { static unsigned cnt = 0; cout << setw ( ITEM_W ) << x << ' '; cnt++; if ( cnt % LSIZE == 0 || cnt == sz ) cout << endl; if ( cnt == sz ) cnt = 0; }

// prints out size and height of bin search tree and // data val in each node in sorted order template < class T > void print_vals ( binSTree < T >& tree ) { // print size and height of tree sz = tree.size ( ); unsigned ht = tree.height ( ); cout << "size of tree = " << sz << endl; cout << "height of tree = " << ht << endl << endl;

// print data values of tree in sorted order tree.inorder ( print ); cout << endl; }

// driver program: to test several member functions // of bin search tree class

int main ( ) { // create 1st vector and fill it with rand ints vector < int > v1 ( N1 ); generate ( v1.begin ( ), v1.end ( ), RND ( SEED1, R ) );

// create 2nd vector and fill it with rand ints vector < int > v2 ( N2 ); generate ( v2.begin ( ), v2.end ( ), RND ( SEED2, R ) );

// create bin search tree with int vals in 1st vector binSTree < int > tree; for (unsigned i = 0; i < v1.size ( ); i++) tree.insert ( v1 [ i ] );

// print vals of bin search tree before removals cout << "Values of bin search tree before removals "; cout << "----------------------------------------- "; print_vals ( tree );

// print vals of 2nd vector in sorted order and // deleting duplicate vals

cout << "Values in 2nd vector in sorted order "; cout << "------------------------------------ "; vector < int > v3 = v2; sort ( v3.begin ( ), v3.end ( ) ); auto p = unique ( v3.begin ( ), v3.end ( ) ); v3.resize ( p - v3.begin ( ) ); sz = v3.size ( ); for_each ( v3.cbegin ( ), v3.cend ( ), print < int > ); cout << endl;

// delete vals in 2nd vector from binary search tree for ( unsigned i = 0; i < v2.size ( ); i++ ) tree.remove ( v2 [ i ] );

// print vals of bin search tree after removals cout << "Values of bin search tree after removals "; cout << "---------------------------------------- "; print_vals ( tree );

return 0; }