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);