# 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; }