/*This program is of creation of AVL Tree for char type data which includes following features:-
1.Create
2.In order
3.Pre order
4.Post order
5.Insert
6.Height of tree
7.Search element
8.Delete element
9.Find minimum
10.Find maximum
#this code is written in turboc++
*/
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<process.h>
struct node
{
int data;
struct node* right,*left;
}*root=NULL;
int height(struct node *ptr )
{
int l,r,h;
if(ptr==NULL)
return -1;
else
{
l=height(ptr->left);
r=height(ptr->right);
h= l>r?l+1:r+1;
}
return h;
}
int balance(struct node *ptr)
{
int l,r,b;
if(ptr==NULL)
return 0;
else
{
l=height(ptr->left);
r=height(ptr->right);
b=l-r;
}
return b;
}
struct node* llrotate(struct node *ptr)
{
struct node *temp;
temp=ptr->left;
ptr->left=temp->right;
temp->right=ptr;
return temp;
}
struct node* rrrotate(struct node *ptr)
{
struct node *temp;
temp=ptr->right;
ptr->right=temp->left;
temp->left=ptr;
return temp;
}
struct node* lrrotate(struct node *ptr)
{
struct node *temp;
temp=ptr->left->right;
ptr->left->right=temp->left;
temp->left=ptr->left;
ptr->left=temp->right;
temp->right=ptr;
return temp;
}
struct node* rlrotate(struct node *ptr)
{
struct node *temp;
temp=ptr->right->left;
ptr->right->left=temp->right;
temp->right=ptr->right;
ptr->right=temp->left;
temp->left=ptr;
return temp;
}
struct node* create(struct node *ptr,int a)
{
if(ptr==NULL)
{
struct node *nn;
nn=(struct node*)malloc(sizeof(struct node));
nn->data=a;
nn->right=NULL;
nn->left=NULL;
ptr=nn;
}
else
{
if((ptr->data)>a)
{
ptr->left=create(ptr->left,a);
if(balance(ptr)==2)
{
if(a<ptr->left->data)
{
ptr=llrotate(ptr);
}
else
{
ptr=lrrotate(ptr);
}
}
}
else if(ptr->data==a)
cout<<"element already exist!\n";
else
{
ptr->right=create(ptr->right,a);
if(balance(ptr)==-2)
{
if(a>ptr->right->data)
{
ptr=rrrotate(ptr);
}
else
{
ptr=rlrotate(ptr);
}
}
}
}
return ptr;
}
struct node* findmin(struct node *ptr)
{
if(ptr->left)
return findmin(ptr->left);
else
return ptr;
}
struct node* findmax(struct node *ptr)
{
if(ptr->right)
return findmax(ptr->right);
else
return ptr;
}
struct node* del(struct node *ptr,int a)
{
if(ptr==NULL)
{
cout<<"Element not present!!"<<endl;
}
else
{
if((ptr->data)>a)
{
ptr->left=del(ptr->left,a);
if(balance(ptr)==-2)
{
if(ptr->right->right)
{
ptr=rrrotate(ptr);
}
else
{
ptr=rlrotate(ptr);
}
}
}
else if(ptr->data==a)
{
struct node *temp;
if(ptr->left&&ptr->right)
{
temp=findmin(ptr->right);
ptr->data=temp->data;
ptr->right=del(ptr->right,ptr->data);
}
else
{
if(ptr->left)
{
temp=findmax(ptr->left);
ptr->data=temp->data;
ptr->left=del(ptr->left,ptr->data);
}
else if(ptr->right)
{
temp=findmin(ptr->right);
ptr->data=temp->data;
ptr->right=del(ptr->right,ptr->data);
}
else
{
temp=ptr;
ptr=NULL;
free(temp);
}
}
}
else
{
ptr->right=del(ptr->right,a);
if(balance(ptr)==2)
{
if(ptr->left->left)
{
ptr=llrotate(ptr);
}
else
{
ptr=lrrotate(ptr);
}
}
}
}
return ptr;
}
void indisplay(struct node *ptr)
{
if(ptr==NULL)
return;
indisplay(ptr->left);
cout<<(char)(ptr->data)<<" ";
indisplay(ptr->right);
}
void predisplay(struct node *ptr)
{
if(ptr==NULL)
return;
cout<<(char)(ptr->data)<<" ";
predisplay(ptr->left);
predisplay(ptr->right);
}
void postdisplay(struct node *ptr)
{
if(ptr==NULL)
return;
postdisplay(ptr->left);
postdisplay(ptr->right);
cout<<(char)(ptr->data)<<" ";
}
struct node* search(struct node *ptr,int a)
{
if(ptr==NULL)
return ptr;
else if(ptr->data>a)
return search(ptr->left,a);
else if(ptr->data<a)
return search(ptr->right,a);
return ptr;
}
void main()
{
int choice;
char ch='j';
char a;
clrscr();
cout<<"1.Create\t2.In order\t3.Pre order\t4.Post order\t5.Insert\t6.Height of tree\t7.Search element\t8.Delete element\t9.Find minimum\t10.Find maximum\t11.Exit"<<endl;
do{
cout<<"Choose a operation which you want to perform:";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter elements(enter ; after last element):";
while(a!=';')
{
cin>>a;
if(a!=';')
root=create(root,(int)(a));
}
break;
case 2:
indisplay(root);
cout<<"\n";
break;
case 3:
predisplay(root);
cout<<"\n";
break;
case 4:
postdisplay(root);
cout<<"\n";
break;
case 5:
cout<<"Enter element which you want to insert:";
cin>>a;
root=create(root,(int)(a));
break;
case 6:cout<<"Height of tree = "<<height(root)<<endl;
break;
case 7:cout<<"Enter element:";
cin>>a;
if(search(root,int(a)))
cout<<"Element found"<<endl;
else
cout<<"Element not found!!"<<endl;
break;
case 8:
cout<<"Enter element which you want to delete:";
cin>>a;
root=del(root,(int)(a));
cout<<"Deletion successful!!\n";
break;
case 9:
cout<<"minimum = "<<(char)(findmin(root)->data)<<"\n";
break;
case 10:
cout<<"maximum = "<<(char)(findmax(root)->data)<<"\n";
break;
case 11:exit(0);
break;
default:cout<<"Wrong entry\n";
}
}while(ch=='j');
}
//ans:- In order: A B C H J K L M P X
| 
| 
