C++

For this computer assignment, implement a derived class (as a template) to represent a binary search tree. Since a binary search tree is a binary tree, implement your binary search tree class from the base class of the binary tree as 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 ); // inserts node with value x bool search ( const T& x ) const; // searches leaf with value x bool remove ( const T& x ); // removes leaf with value x private: void insert ( Node < T >*&, const T& ); // private version of insert bool search ( Node < T >*, const T& ) const;// private version of search void remove ( Node < T >*&, const T& ); // private version of remove bool leaf ( Node < T >* node ) const; // checks if node is leaf }; The insert ( ) function inserts a node with the data value x in the tree. For the search ( ) function, x is the data value of a leaf to be searched for. If the search is successful, the search ( ) function returns true; otherwise, it returns false. The remove ( ) function first calls the search ( ) function to determine the result of the search for a leaf with the data value x, and if the search is successful, then it calls the private version of the remove ( ) function to remove the corresponding leaf from the tree and returns true; otherwise, it returns false. The leaf ( ) function simply checks if a node is a leaf. The private versions of the member functions insert ( ), remove ( ) and search ( ) can be implemented as recursive functions, but these functions have an additional argument, which is the root of the tree. The private version of the remove ( ) function unlike its public version does not return any value. To test your derived class and its member functions, the source file of a driver program prog7.cc and its header file prog7.h, in directory: ~courses/cs340/progs/18f/p7, are provided. This program generates a set of random integers in the range [1 N ] with N = 100 and inserts them in a vector of integers and in a binary search tree. The program searches for each value of the vector in the binary search tree. If the value can be found as the data value of a leaf, then the leaf is removed from the tree. After removing all the leaves, the size of the tree and the data Binary Search Trees and Tree Sort 2 values in nodes are printed in ascending order by traversing the tree in inorder. This process continues until the tree becomes completely empty. Put the implementation of your binary search tree class in a separate header file, say binSTree.h. To use the class Node in your program, include the header file Node.h, by inserting the statement: #include /home/cs340/progs/18f/p7/Node.h, at the top of 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 other header files (if any) #ifndef constantvalue #define constantvalue // statements in header file #endif For each header file, use a different constantvalue. To compile and link the driver program with the system library routines, execute: Make N=7. To test your binary-search-tree class, execute: Make execute N=7. This command executes the driver program and displays the output as well as any error messages both on the terminal screen and in prog7.out. After you are done with the program, you dont need its object and executable files any more. To delete them, execute: Make clean. The correct output of this program can be found in file prog7.out, which is in the same directory with prog7.cc. If the program fails to generate the correct output, then to debug the program, copy the file prog7.cc in your own directory, uncomment some of the statements in that file, recompile and link the modified program, and then execute again. When your program is ready, submit your header files to your TA, by executing: mail_prog.340 binTree.h binSTree.h. Note: In public versions of insert ( ), remove ( ) and search ( ) functions, youll get a compile error when you pass the root as an argument to these functions. To eliminate the compile errors, you need to pass the root as this>root.