Program to show the implementation of Binary Search Tree as Sets

 # include <iostream.h>
 # include   <stdlib.h>
 # include   <string.h>
 # include    <conio.h>

 /**************************************************************************/
 //--------------------------  Class Definition  --------------------------//
 /**************************************************************************/

 //--------------------------------  Set  ---------------------------------//

 class Set
 {
    private:
       int data;
       int size;

       static int flag;
       static int value;
       static int cur;

       Set *LeftNode;
       Set *RightNode;

    public:
       Set *RootNode;
       Set *Location;
       Set *Parent;

       Set( );
       Set* InsertElement(Set*, const int);
       void DeleteElementWith0Or1Child( );
       void DeleteElementWith2Child( );
       void getElementAtPos(Set*, const int);
       int getElementAt(Set*, const int);
       void Print(Set*);
       void Print( );
       void PrintAscending(Set*);
       void PrintDescending(Set*);

       int Size( );
       void Empty( );
       int IsEmpty( );
       void Read(const char*);
       void AddElement(const int);
       void DeleteElement(const int);
       void PrintAscending( );
       void PrintDescending( );
       int IsAnElement(const int);
       Set Union(const Set set);
       Set Intersection(const Set set);
       int IsASubSet(const Set subset);
       int operator==(const Set set);
       Set operator-(const Set set);
 };

 int Set::flag = 1;
 int Set::value = 0;
 int Set::cur = 0;


 //------------------------  Function Definitions  -----------------------//


 //-------------------------------  Set( )  ------------------------------//

 Set::Set( )
 {
    RootNode = NULL;
    LeftNode = NULL;
    RightNode = NULL;

    data = 0;
    size = 0;
 }

 //--------------------------  InsertElement( )  ------------------------//

 Set* Set::InsertElement(Set *Node, const int data)
 {
    if (Node == NULL)
    {
       Set *Temp;

       Temp = new Set;

       Temp->data = data;
       Node = Temp;
       Node->LeftNode = NULL;
       Node->RightNode = NULL;

       size ++;
    }

    else
    {
       Parent = Node;

       if (data > Node->data)
       {
      if (Node->RightNode == NULL)
         Node->RightNode = InsertElement(Node->RightNode, data);

      else
         InsertElement(Node->RightNode, data);
       }

       else
       {
      if (Node->LeftNode == NULL)
         Node->LeftNode = InsertElement(Node->LeftNode, data);

      else
         InsertElement(Node->LeftNode,data);
       }
    }

    return Node;
 }

 //------------------------------  Size( )  -------------------------------//

 int Set::Size( )
 {
    return size;
 }

 //-----------------------------  IsEmpty( )  -----------------------------//

 int Set::IsEmpty( )
 {
    if (RootNode == NULL)
       return 1;

    return 0;
 }

 //-------------------------------  Empty( )  -----------------------------//

 void Set::Empty( )
 {
    for (int i = size; i >= 1; i--)
    {
       int num = getElementAt(RootNode, i);

       flag = 0;

       DeleteElement(num);

       flag = 1;
    }

    RootNode = NULL;
    size = 0;
 }

 //---------------------------  getElementAtPos( )  -----------------------//

 void Set::getElementAtPos(Set *Node, const int req)
 {
    cur ++;

    if (cur == req)
       value = Node->data;

    if (Node->LeftNode != NULL)
       getElementAtPos(Node->LeftNode, req);

    if (Node->RightNode != NULL)
       getElementAtPos(Node->RightNode, req);
 }

 int Set::getElementAt(Set* Node, const int req)
 {
    value = 0;
    cur = 0;

    getElementAtPos(Node, req);

    return value;
 }

 //----------------------------------  Print( )  --------------------------//

 void Set::Print(Set *Node)
 {
    if (Node == NULL)
    {  }

    else
    {
       cout << \" \" << Node->data;

       if (Node->LeftNode != NULL)
      Print(Node->LeftNode);

       if (Node->RightNode != NULL)
      Print(Node->RightNode);
    }
 }

 void Set::Print( )
 {
    Print(RootNode);
 }

 //---------------------------  PrintAscending( )  ------------------------//

 void Set::PrintAscending(Set *Node)
 {
    if (Node==NULL)
    {  }

    else
    {
       if (Node->LeftNode != NULL)
      PrintAscending(Node->LeftNode);

       cout << \" \" << Node->data;

       if (Node->RightNode != NULL)
      PrintAscending(Node->RightNode);
    }
 }

 void Set::PrintAscending( )
 {
    PrintAscending(RootNode);
 }

 //---------------------------  PrintDescending( )  -----------------------//

 void Set::PrintDescending(Set *Node)
 {
    if (Node == NULL)
    {  }

    else
    {
       if (Node->RightNode != NULL)
      PrintDescending(Node->RightNode);

       cout << \" \" << Node->data;

       if (Node->LeftNode != NULL)
      PrintDescending(Node->LeftNode);
    }
 }

 void Set::PrintDescending( )
 {
    PrintDescending(RootNode);
 }

 //---------------------------  IsAnElement( )  ---------------------------//

 int Set::IsAnElement(const int key)
 {
    int depth = 1;
    int left_right = 0;

    Set *Pointer = NULL;
    Set *Save = NULL;

    Location = NULL;
    Parent = NULL;

    if (RootNode == NULL)
    {
       Location = NULL;
       Parent = NULL;
    }

    else if (key == RootNode->data)
    {
       Location = RootNode;
       Parent = NULL;

       depth = 1;
    }

    else
    {
       if (key < RootNode->data)
       {
      Pointer = RootNode->LeftNode;

      left_right = 1;
       }

       else
       {
      Pointer = RootNode->RightNode;

      left_right = 2;
       }

       Save = RootNode;

       while (Pointer != NULL)
       {
      depth += 1;

      if (key == Pointer->data)
      {
         Location = Pointer;
         Parent = Save;

         break;
      }

      else if(key < Pointer->data)
      {
         Save = Pointer;
         Pointer = Pointer->LeftNode;
      }

      else if(key > Pointer->data)
      {
         Save = Pointer;
         Pointer = Pointer->RightNode;
      }
       }
    }

    if (flag == 1)
    {
       if (Location == NULL)
       {
      Parent = NULL;

      cout << \"\\n\\n*** \" << key << \" is not found in the Set. \" << endl;
       }

       else if (Location != NULL)
       {
      if (left_right == 0)
         cout << \"\\n\\n*** \" << key << \" is the Root Node.\" << endl;

      else if (left_right == 1)
         cout << \"\\n\\n*** \" << key << \" lies at the Left side of the Root Node \";

      else if (left_right == 2)
         cout << \"\\n\\n*** \" << key << \" lies at the Right side of the Root Node \";

      if (left_right)
         cout << \"and at the depth level \" << depth << endl;
       }
    }

    if (Location != NULL)
       return 1;

    return 0;
 }

 //--------------------  DeleteElementWith0Or1Child( )  -------------------//

 void Set::DeleteElementWith0Or1Child( )
 {
    Set *Child;

    if (Location->LeftNode == NULL && Location->RightNode == NULL)
       Child = NULL;

    else if (Location->LeftNode != NULL)
       Child = Location->LeftNode;

    else
       Child = Location->RightNode;

    if (Parent != NULL)
    {
       if (Location == Parent->LeftNode)
      Parent->LeftNode = Child;

       else
      Parent->RightNode = Child;
    }

    else
       RootNode = Child;
 }

 //----------------------  DeleteElementWith2Child( )  --------------------//

 void Set::DeleteElementWith2Child( )
 {
    Set *Pointer = Location->RightNode;
    Set *Save = Location;

    Set *Sucessor;
    Set *Parent_sucessor;

    while (Pointer->LeftNode != NULL)
    {
       Save = Pointer;
       Pointer = Pointer->LeftNode;
    }

    Sucessor = Pointer;
    Parent_sucessor = Save;

    Set *temp_loc = Location;
    Set *temp_par = Parent;

    Location = Sucessor;
    Parent = Parent_sucessor;

    DeleteElementWith0Or1Child( );

    Location = temp_loc;
    Parent = temp_par;

    if (Parent != NULL)
    {
       if (Location == Parent->LeftNode)
      Parent->LeftNode = Sucessor;

       else
      Parent->RightNode = Sucessor;
    }

    else
       RootNode = Sucessor;

    Sucessor->LeftNode = Location->LeftNode;
    Sucessor->RightNode = Location->RightNode;
 }

 //--------------------------  DeleteElement( )  --------------------------//

 void Set::DeleteElement(const int key)
 {
    IsAnElement(key);

    if (RootNode == NULL)
    {
       if (flag == 1)
      cout << \"\\n\\n*** Error : Set is empty. \\n\" << endl;
    }

    else if (Location == NULL)
    {
       if (flag == 1)
      cout << \"\\n\\n*** \" << key << \"  does not exists in the Set \\n\" << endl;
    }

    else
    {
       if (Location->RightNode != NULL && Location->LeftNode != NULL)
      DeleteElementWith2Child( );

       else
      DeleteElementWith0Or1Child( );

       size --;

       if (flag == 1)
      cout << \"*** \" << key << \" is deleted from the Set.\" << endl;
    }
 }

 //----------------------------  AddElement( )  ---------------------------//

 void Set::AddElement(const int num)
 {
    if (RootNode == NULL)
       RootNode = InsertElement(RootNode, num);

    else
    {
       flag = 0;

       IsAnElement(num);

       flag = 1;

       if (Location==NULL)
      InsertElement(RootNode, num);
    }
 }

 //--------------------------------  Read( )  -----------------------------//

 void Set::Read(const char* Numbers)
 {
    char Temp[255] = {NULL};

    strcpy(Temp, Numbers);

    char* Ptr = strtok(Temp,\",\");

    int num = 0;

    flag = 0;

    while (Ptr != NULL)
    {
       num = atoi(Ptr);

       AddElement(num);

       Ptr = strtok(NULL, \",\");
    }

    flag = 1;
 }

 //----------------------------------  Union( )  --------------------------//

 Set Set::Union(const Set set)
 {
    Set C;

    flag = 0;

    for (int i = 1; i <= size; i ++)
       C.AddElement(getElementAt(RootNode, i));

    for (int j = 1; j <= set.Size( ); j ++)
       C.AddElement(getElementAt(set.RootNode, j));

   flag = 1;

    return C;
 }

 //---------------------------  Intersection( )  --------------------------//

 Set Set::Intersection(const Set set)
 {
    Set C;

    for (int i = 1; i <= size; i ++)
    {
       int num = getElementAt(RootNode, i);

       flag = 0;

       if (set.IsAnElement(num) == 1)
      C.AddElement(num);

       flag = 1;
    }

    return C;
 }

 //----------------------------  Operator==( )  ---------------------------//

 int Set::operator==(const Set set)
 {
    if (size != set.Size( ))
       return 0;

    int eFlag = 1;

    for (int i = 1; i <= size; i ++)
    {
       int num = getElementAt(RootNode, i);

       flag = 0;

       if (set.IsAnElement(num) == 0)
       {
      eFlag = 0;

      break;
       }

       flag = 1;
    }

    return eFlag;
 }

 //-----------------------------  Operator-( )  ---------------------------//

 Set Set::operator-(const Set set)
 {
    Set C;

    for (int i = 1; i <= size; i ++)
       C.AddElement(getElementAt(RootNode, i));

    for (int j = 1; j <= set.Size( ); j ++)
    {
       int num = getElementAt(set.RootNode, j);

       flag = 0;

       C.DeleteElement(num);

       flag = 1;
    }

    return C;
 }

 //-----------------------------  IsASubSet( )  ---------------------------//

 int Set::IsASubSet(const Set subset)
 {
    if (size == 0)
       return 0;

    if (subset.Size( ) == 0)
       return 1;

    int eFlag = 1;

    for (int i = 1; i <= size; i ++)
    {
       int num = getElementAt(subset.RootNode, i);

       flag = 0;

       if (IsAnElement(num) == 0)
       {
      eFlag = 0;
      break;
       }

       flag = 1;
    }

    return eFlag;
 }


 //-------------------------------  main( )  -----------------------------//


 int main( )
 {
    clrscr( );

    Set A;

    cout << \"Read() & AddElement() Demonstration\" << endl;
    cout << \"***********************************\" << endl;

    cout << \"\\nRead(\\\"5,3,1,2,0\\\")\" << endl;
    A.Read(\"5,3,1,2,0\");

    cout << \"AddElement(4)\" << endl;
    cout << \"AddElement(9)\" << endl;
    cout << \"AddElement(4)\" << endl;
    A.AddElement(4);
    A.AddElement(9);
    A.AddElement(4);

    cout << \"\\nSet A =\";
    A.Print( );

    getch( );

    cout << \"\\n\\n\\nPrintAscending() Demonstration\" << endl;
    cout << \"******************************\" << endl;

    cout << \"\\nAscending Order :\";
    A.PrintAscending( );

    getch( );

    cout << \"\\n\\n\\nPrintDescending() Demonstration\" << endl;
    cout << \"*******************************\" << endl;

    cout << \"\\nDescending Order :\";
    A.PrintDescending( );

    getch( );

    cout << \"\\n\\n\\nDeleteElement() Demonstration\" << endl;
    cout << \"*****************************\" << endl;

    cout << \"DeleteElement(5)\" << endl;
    A.DeleteElement(5);

    cout << \"\\nSet =\";
    A.Print( );

    getch( );

    cout << \"\\n\\n\\nIsAnElement() Demonstration\" << endl;
    cout << \"***************************\" << endl;

    A.IsAnElement(2);

    getch( );

    cout << \"\\n\\n\\nSize() Demonstration\" << endl;
    cout << \"********************\" << endl;

    cout << \"\\nSet Size = \" << A.Size( ) << endl;

    getch( );

    cout << \"\\n\\n\\nIsEmpty() Demonstration\" << endl;
    cout << \"******************************\" << endl;

    if (A.IsEmpty( ) == 1)
       cout << \"\\nThe Set is Empty\" << endl;

    else
       cout << \"\\nThe Set Is Not Empty\" << endl;

    getch( );

    cout << \"\\n\\n\\nUnion() Demonstration\" << endl;
    cout << \"*********************\" << endl;

    Set B, C;

    B.Read(\"1,7,0,4,6,8,5\");

    cout << \"\\nSet A =\";
    A.Print( );

    cout << \"\\nSet B =\";
    B.Print( );

    C = A.Union(B);

    cout << \"\\n\\nC = A u B =\";
    C.Print( );

    getch( );

    cout << \"\\n\\n\\nIntersection() Demonstration\" << endl;
    cout << \"****************************\" << endl;

    C = A.Intersection(B);

    cout << \"\\n\\nC = A n B =\";
    C.Print( );

    getch( );

    cout << \"\\n\\n\\nEmpty() Demonstration\" << endl;
    cout << \"*********************\" << endl;

    C.Empty( );

    if (C.IsEmpty( ) == 1)
       cout << \"\\n\\nThe Set C is Empty\" << endl;

    else
       cout << \"\\n\\nThe Set C Is Not Empty\" << endl;

    getch( );

    cout << \"\\n\\n\\nOperator == Demonstration\" << endl;
    cout << \"*************************\" << endl;

    if (A == B)
      cout << \"\\nSet A = Set B\" << endl;

    else
      cout << \"\\nSet A != Set B\" << endl;

    getch( );

    cout << \"\\n\\n\\nOperator - Demonstration\" << endl;
    cout << \"************************\" << endl;

    C = (A - B);

    cout << \"\\nC = A - B = \";
    C.Print( );

    getch( );

    cout << \"\\n\\n\\nIsASubSet() Demonstration\" << endl;
    cout << \"*************************\" << endl;

    B.Empty( );

    B.Read(\"4,1,2\");

    cout << \"\\n\\nSet A =\";
    A.Print( );

    cout << \"\\nSet B =\";
    B.Print( );

    if (A.IsASubSet(B) == 1)
       cout << \"\\n\\nSet B is a Subset of Set A\" << endl;

    else
       cout << \"\\n\\nSet B is not Subset of Set A\" << endl;

    getch( );
    return 0;
 }