Implement the Set ADT in a file Set.h as shown below. This data stucture will be implementated on the basis of Binary Search Trees. In fact, our Set is a Binary Search Tree.

// Set.h // after Mark A. Weiss, Chapter 4, Dr. Kerstin Voigt #ifndef SET_H #define SET_H #include #include #include using namespace std; template class Set { public: Set( ) : root{ nullptr } { } ~Set( ) { makeEmpty(); } const C & findMin( ) const { assert(!isEmpty()); return findMin( root )->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 root == nullptr; } void printSet( ) const { if( isEmpty( ) ) cout  // add nested class iterator here // private: // Internal method to insert into a subtree. // x is the item to insert. // t is the node that roots the subtree. // Set the new root of the subtree. void insert( const C & x, BinaryNode* & t ) { if( t == nullptr ) t = new BinaryNode{ x, nullptr, nullptr }; else if( x element ) insert( x, t->left ); else if( t->element right ); else ; // 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 ) return; // Item not found; do nothing if( x element ) remove( x, t->left ); else if( t->element right ); else if( t->left != nullptr && t->right != nullptr ) // Two children { t->element = findMin( t->right )->element; remove( t->element, t->right ); } else { BinaryNode* oldNode = t; t = ( t->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( t == nullptr ) return nullptr; if( t->left == nullptr ) return t; return findMin( t->left ); } // 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. // x is item to search for. // t is the node that roots the subtree. bool contains( const C & x, BinaryNode* t ) const { if( t == nullptr ) return false; else if( x element ) return contains( x, t->left ); else if( t->element right ); else return true; // Match } void makeEmpty( BinaryNode* & t ) { if( t != nullptr ) { makeEmpty( t->left ); makeEmpty( t->right ); delete t; } t = nullptr; } void printSet( BinaryNode* t) const { if( t != nullptr ) { printSet( t->left); cout element right); } } }; #endif

Program your own file main.cpp in which your main() function will test the new data structure.

• The main function is contained in the file main.cpp.
• Declare an instance of Set 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 printSet() member function in order to print out the values in your set.
• Prompt user to enter a random sequence of integer values, remove these values from your set. Print out the reduced set.

Add the following nested class iterator in your Set class template. Please iterator class after the private data member.

class iterator { public: iterator() : current(nullptr) {} C & operator *() { return current->element; } iterator & operator++() { if (current == nullptr) return *this; if (current->right != nullptr) { current = current->right; while (current->left != nullptr) { antes.push(current); current = current->left; } } else { if (!antes.empty()) { current = antes.top(); antes.pop(); } else current = nullptr; } return *this; } iterator operator++(int) { iterator old = *this; ++(*this); return old; } bool operator ==(const iterator & rhs) const { return current == rhs.current; } bool operator !=(const iterator & rhs) const { return !(*this == rhs); } private: BinaryNode * current; stack antes; iterator(BinaryNode* p, stack st) : current{p}, antes{st} {} friend class Set; }; iterator begin() { BinaryNode* lmost = root; stack nstack; while (lmost->left != nullptr) { nstack.push(lmost); lmost = lmost->left; } return iterator(lmost,nstack); } iterator end() { stack emptystack; return iterator(nullptr, emptystack); }

Go back to your program main.cpp and use iterator to print the element values in your set. Compile and run your program, and see what you get.

The expected result:

NOTE: please write down the code for the TWO files :

1- Set.h: the implementation file of the Set class template.

2- main.cpp: the test file containing main() funcion.

3- show me your output

Thank you.

insert the values (stop when entering 0): 10 5 20 3 22 6 18 79 13 15 4 2 119 30 8 0 print the values: 1 2 3-4- 5-6-7 -8 9-10 13 15 18 -19 20 22 30- remove the values (stop when entering 0): 1 11 2 12 3 13 0 print the values: 4-5-6 7-8 -9 10 15-18 -19 -20 - 22 30- Print the element values using iterator 4,5, 6, 7, 8, 9, 10, 15, 18, 19, 20, 22, 30 insert the values (stop when entering 0): 10 5 20 3 22 6 18 79 13 15 4 2 119 30 8 0 print the values: 1 2 3-4- 5-6-7 -8 9-10 13 15 18 -19 20 22 30- remove the values (stop when entering 0): 1 11 2 12 3 13 0 print the values: 4-5-6 7-8 -9 10 15-18 -19 -20 - 22 30- Print the element values using iterator 4,5, 6, 7, 8, 9, 10, 15, 18, 19, 20, 22, 30