Logo 
Search:

C++ Programming Articles

Submit Article
Home » Articles » C++ Programming » Data File StructureRSS Feeds

Program to show the implementation of Binary Search Tree as Sets

Posted By: Easy Tutor     Category: C++ Programming     Views: 6901

A C++ Program to show the implementation of Binary Search Tree as Sets.

Code for Program to show the implementation of Binary Search Tree as Sets in C++ Programming

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

 /**************************************************************************///--------------------------  Class Definition  --------------------------///**************************************************************************///--------------------------------  Set  ---------------------------------//class Set
 {
    private:
       int data;
       int size;

       staticint flag;
       staticintvalue;
       staticint cur;

       Set *LeftNode;
       Set *RightNode;

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

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

       int Size( );
       void Empty( );
       int IsEmpty( );
       void Read(constchar*);
       void AddElement(constint);
       void DeleteElement(constint);
       void PrintAscending( );
       void PrintDescending( );
       int IsAnElement(constint);
       Set Union(const Set set);
       Set Intersection(const Set set);
       int IsASubSet(const Set subset);
       intoperator==(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, constint 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, constint 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, constint req)
 {
    value = 0;
    cur = 0;

    getElementAtPos(Node, req);

    returnvalue;
 }

 //----------------------------------  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(constint 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;
    }

    elseif (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;
      }

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

      elseif(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;
       }

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

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

      elseif (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;

    elseif (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(constint key)
 {
    IsAnElement(key);

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

    elseif (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(constint 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(constchar* 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;
 }
  
Share: 



Easy Tutor
Easy Tutor author of Program to show the implementation of Binary Search Tree as Sets is from United States. Easy Tutor says

Hello Friends,

I am Free Lance Tutor, who helped student in completing their homework.

I have 4 Years of hands on experience on helping student in completing their homework. I also guide them in doing their final year projects.

I have share many programs on this website for everyone to use freely, if you need further assistance, than please contact me on easytutor.2ya [at the rate] gmail [dot] com

I have special discount scheme for providing tutor services. I am providing tutor service to students from various contries, currently most of my students are from United States, India, Australia, Pakistan, Germany, UK and Canada.

I am also here to expand my technical network to receive more opportunity in my career, make friends to help them in resolving their technical problem, learn and share my knowledge, If you like to be my friend, Please send me friend request.

Thanks,
Happy Programming :)

 
View All Articles

 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
No Comment Found, Be the First to post comment!