Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

In C++ and use functions it asks for. Thanks

image text in transcribedimage text in transcribedimage text in transcribedimage text in transcribedimage text in transcribed

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

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

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

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

More Books

Students also viewed these Databases questions