Exercise 1:

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 << "Empty set" << endl; else printSet( root ); } void makeEmpty( ) { makeEmpty( root ); } void insert( const C & x ) { insert( x, root ); } void remove( const C & x ) { remove( x, root ); } private: struct BinaryNode { C element; BinaryNode* left; BinaryNode* right; BinaryNode( const C & theElement, BinaryNode* lt, BinaryNode* rt ) : element{ theElement }, left{ lt }, right{ rt } { } }; BinaryNode* root; public: //  // 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 < t->element ) insert( x, t->left ); else if( t->element < x ) insert( x, t->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 < t->element ) remove( x, t->left ); else if( t->element < x ) remove( x, t->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 < t->element ) return contains( x, t->left ); else if( t->element < x ) return contains( x, t->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 << t->element << " - "; printSet( t->right); } } }; #endif 

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

• The main function is contained in the file lab08.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.

Exercise 2:

• 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 lab08.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:

insert the values (stop when entering 0): 10 5 20 3 22 6 18 7 9 13 15 4 2 1 19 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,

PLEASE MAKE SURE YOUR ANSWER INCLUDES IMPLEMENTATION OF SET.H