In C++ and use functions it asks for. Thanks
Implement the BinarySearchTree ADT in a file BinarysearchTree.h exactly as shown below // BinarySearchTree.h // after Mark A. Weiss, Chapter 4, Dr. Kerstin Voigt #ifndef BINARY SEARCH TREE H #define BINARY SEARCH TREE H #include
using namespace std; template element; const C& findMax( const assert(!isEmpty ()); return findMax( root )->element; bool contains( const C& x ) const return contains( x, root); bool isEmpty const return rootnullptr; void printTree( ) const if( isEmpty()) out element else if( t->element right ); ; // 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 C&x, BinaryNode* & t ) if( t nullptr if( x element) else if( t->element leftnullptr && t->rightnullptr) // Two children return; // Item not found; do nothing remove( x, t-left); remove( x, t->right); t->element-findMin( t->right)->element; remove( t->element, t->right ); else BinaryNode oldNodet; tt-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 nullptr) if( t->leftnullptr) return findMin( t->left ; return nullptr; return t; // 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 // is item to search for. // t is the node that roots the subtree. bool contains const C& x, BinaryNode t ) const if( t nullptr else if( x element) else if( t->element left); return contains( x, t->right ); return true; /Match void makeEmpty BinaryNode* & t ) if( t nullptr makeEmpty( t->left); makeEmpty( t->right ); delete t; t- nullptr; void printTree( BinaryNode* t) const if( t nullptr printTree( t-left); cout element right); d; #endif Exercise 2: Program your own file labe7.cpp n which your main0 unction will test the new data structure The main function is contained in the file lab07.cpp Declare an instance of BinarySearchTree (short: BST) suitable to hold integer values. Prompt user to enter a random sequence of integer values, insert these values into the data structure (the entered values should NOT be in sorted order) Call the printTree()member function in order to print out the values of the BST structure Prompt user to enter a random sequence of integer values, remove these values from your BST. Print out the reduced BST Exercise 3: Add the following member function in your BinarySearchTree class template. public: void printInternal() print_Internal(root,0); private: void printInternal (BinaryNode* t, int offset) if (tnullptr) return; for(int i-l; i offset; i++) cout element right, offset + 1); Go back to your program lab07.cpp and call printInternal. Compile and run your program, and see what you get. The expected result: insert the values (stop when entering 0): 10 5 20 3 22 6 18 79 13 15 4 2 1 19 30 8 0 print the values: 1-2 -3-4-5- 6- 7-8-9 1013 1518- 19 - 20 - 22- 30 Print the tree: 4 remove the values (stop when entering ): 1 11 2 12 3 13 0 print the values: 4-5- 6- 7- 8 - 9- 1015 18-19 - 20 - 22- 30 - Print the tree