In C++

Implement class Set using a binary search tree by modifying

the textbook BinarySearchTree class (Figures 4.16, 4.17, 4.18,

4.20, 4.21, 4.23, 4.26, 4.27, and 4.28) as follows:

1) Add data member Size.

2) Add nested classes const_iterator and iterator with the

same members as those of Figures 3.14 and 3.15.

3) Add methods begin() and end().

4) Add to each node a link to the parent node. (This is

needed by operator++ in the iterators.)

Include a main function that instantiates a set of integers,

Set, and allows an interactive user to execute any

of the member functions and to print the contents of the

set using an iterator (Figure 3.6).

2 31 4 3 6 7 Figure 4.16 1 template class BinarySearch Tree public: BinarySearchTree(); BinarySearchTree( const BinarySearchTree & rhs); -BinarySearchTree(); 8 9 const Comparable & findMin() const; 10 const Comparable & findMax() const; 11 bool contains(const Comparable & x ) const; 12 bool isEmpty() const; 13 void print Tree() const; 14 15 void makeEmpty(); 16 void insert( const Comparable & x ); 17 void remove( const Comparable & x); 18 19 20 21 22 23 1 24 25 26 27 28 29 30 }; 31 32 const BinarySearchTree & operator-( const BinarySearchTree & rhs); private: struct BinaryNode Comparable element; BinaryNode "left: BinaryNode right; BinaryNode( const Comparable & theElement, BinaryNode *1t, BinaryNode *rt) element (the Element ), left( 1t ), right ( rt) { }) BinaryNode root; 33 34 35 void insert(const Comparable & x, BinaryNode & t ) const; void remove( const Comparable & x, BinaryNode & t ) const; 36 37 BinaryNode *findMin( BinaryNode *t) const; BinaryNode *findMax( BinaryNode *t) const; 38 bool contains( const Comparable & x, BinaryNode *t) const; 39 void makeEmpty(BinaryNode & t); 40 void print Tree( BinaryNode *+) const; 41 BinaryNode * clone( BinaryNode *t) const; 42 }; Figure 4.16 Binary search tree class skeleton lll 590