Code:
#include iostream
#include cstdlib
#define MAX_ELEMS 25
using namespace std;
/*
* Node Declaration
*/
struct node
{
int k;
node *left;
node *right;
};
typedef node *tree;
/*
* Merging two trees
*/
tree merge(tree a,tree b )
{
tree bota, botb, r, temp;
if (a == NULL)
return b;
else if (b == NULL)
return a;
else
{
bota = a->right;
a->right = NULL;
botb = b->left;
b->left = NULL;
r = NULL;
while (bota != NULL && botb != NULL)
{
if (bota->k < botb->k)
{
temp = bota->right;
if (r == NULL)
bota->right = bota;
else
{
bota->right = r->right;
r->right = bota;
}
r = bota;
bota = temp;
}
else
{
temp = botb->left;
if (r == NULL)
botb->left = botb;
else
{
botb->left = r->left;
r->left = botb;
}
r = botb;
botb = temp;
}
}
if (botb == NULL)
{
a->right = r->right;
r->right = bota;
return a;
}
else
{
b->left = r->left;
r->left = botb;
return b;
}
}
}
/*
* Insert element into pagoda
*/
tree insert(tree node, tree pq)
{
node->left = node;
node->right = node;
return merge(pq, node);
}
/*
* Delete element from pagoda
*/
tree del(tree pq)
{
tree le, ri;
if (pq == NULL)
{
cout<<"Deletion out of range"<
return NULL;
}
else
{
if (pq->left == pq)
le = NULL;
else
{
le = pq->left;
while (le->left != pq)
le = le->left;
le->left = pq->left;
}
if (pq->right == pq)
ri = NULL;
else
{
ri = pq->right;
while (ri->right != pq)
ri = ri->right;
ri->right = pq->right;
}
return merge(le, ri);
}
}
/*
* Main Contains Menu
*/
int main()
{
node **root = new node* [MAX_ELEMS + 1];
int value, i = 0;
int choice;
while(1)
{
cout<<"\n----------------------"<
cout<<"Operations on Pagoda"<
cout<<"\n----------------------"<
cout<<"1.Insert element at Last"<
cout<<"2.Display Pagoda"<
cout<<"3.Delete Last element"<
cout<<"4.Exit"<
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
{
cout<<"Enter element "<
cin>>value;
node *temp = new node;
temp->k = value;
root[i] = insert(temp, root[i]);
i++;
break;
}
case 2:
{
cout<<"Displaying elements of pagoda: "<
int j = 0;
while(root[j] != NULL)
{
cout<<"Element "<
j++;
}
break;
}
case 3:
root[i - 1] = del(root[i - 1]);
i--;
break;
case 4:
exit(1);
default:
cout<<"Wrong Choice"<
}
}
return 0;
}
Output:
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 1
Enter element 1: 5
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 2
Displaying elements of pagoda:
Element 1: 5
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 1
Enter element 2: 4
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 1
Enter element 3: 6
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 1
Enter element 4: 8
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 1
Enter element 5: 11
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 2
Displaying elements of pagoda:
Element 1: 5
Element 2: 4
Element 3: 6
Element 4: 8
Element 5: 11
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 3
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 2
Displaying elements of pagoda:
Element 1: 5
Element 2: 4
Element 3: 6
Element 4: 8
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 1
Enter element 5: 15
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 3
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 2
Displaying elements of pagoda:
Element 1: 5
Element 2: 4
Element 3: 6
Element 4: 8
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 1
Enter element 5: 100
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 2
Displaying elements of pagoda:
Element 1: 5
Element 2: 4
Element 3: 6
Element 4: 8
Element 5: 100
----------------------
Operations on Pagoda
----------------------
1.Insert element at Last
2.Display Pagoda
3.Delete Last element
4.Exit
Enter your choice: 4
------------------
(program exited with code: 1)
Press return to continue
More C++ Programs:
