program for avl tree

//program for avl tree
#include< stdio.h >
#include< conio.h >
#include< alloc.h >
#include< string.h >
typedef enum{FALSE,TRUE} bool;
struct node
{
char name[10];
struct node* left;
struct node* right;
int bf;
};
void display(struct node* parent,int level)
{
int i;
if(parent!=NULL)
{
display(parent->right,level+1);
printf("\n");
for(i=0;i printf(" ");
printf("%s",parent->name);
display(parent->left,level+1);
}
}
void inorder(struct node* parent)
{
if(parent!=NULL)
{
inorder(parent->left);
printf("\n%s\n",parent->name);
inorder(parent->right);
}
}
struct node* search(struct node* ptr,char* name)
{
if(ptr!=NULL)
if(strcmp(name,ptr->name)<0)
ptr=search(ptr->left,name);
else if(strcmp(name,ptr->name)>0)
ptr=search(ptr->right,name);
return(ptr);
}
struct node* insert(char* name,struct node* pptr,int* htinc)
{
struct node *aptr;
struct node* bptr;
if(pptr==NULL)
{
pptr=(struct node*)malloc(sizeof(struct node));
strcpy(pptr->name,name);
pptr->left=NULL;
pptr->right=NULL;
pptr->bf=0;
*htinc=TRUE;
return(pptr);
}
if(strcmp(name,pptr->name)<0)
{
pptr->left=insert(name,pptr->left,htinc);
if(*htinc==TRUE)
{
switch(pptr->bf)
{
case -1:
pptr->bf=0;
*htinc=FALSE;
break;
case 0:
pptr->bf=1;
break;
case 1:
aptr=pptr->left;
if(aptr->bf==1)
{
printf("LL rotation");
pptr->left=pptr->right;
aptr->right=pptr;
pptr->bf=0;
aptr->bf=0;
pptr=aptr;
}
else
{
printf("LR roteation");
bptr=aptr->right;
aptr->right=bptr->left;
bptr->left=aptr;
pptr->left=bptr->right;
bptr->right=pptr;
if(bptr->bf==1)
pptr->bf=1;
else
pptr->bf=0;
if(bptr->bf==-1)
aptr->bf=1;
else
aptr->bf=0;
bptr->bf=0;
pptr=bptr;
}
*htinc=FALSE;
}
}
}
if(strcmp(name,pptr->name)>0)
{
pptr->right=insert(name,pptr->right,htinc);
if(*htinc==TRUE)
{
switch(pptr->bf)
{
case 1:
pptr->bf=0;
*htinc=FALSE;
break;
case 0:
pptr->bf=-1;
break;
case -1:
aptr=pptr->right;
if(aptr->bf==-1)
{
printf("RR rotation");
pptr->right=pptr->left;
aptr->left=pptr;
pptr->bf=0;
aptr->bf=0;
pptr=aptr;
}
else
{
printf("RL roteation");
bptr=aptr->left;
aptr->left=bptr->right;
bptr->right=aptr;
pptr->right=bptr->left;
bptr->right=pptr;
if(bptr->bf==-1)
pptr->bf=1;
else
pptr->bf=0;
if(bptr->bf==1)
aptr->bf=-1;
else
aptr->bf=0;
bptr->bf=0;
pptr=bptr;
}
*htinc=FALSE;
}
}
}
return(pptr);
}
void main()
{
struct node* root;
int choice;
char name[10];
bool htinc;
clrscr();
root=(struct node*)malloc(sizeof(struct node));
root=NULL;
printf("\n\n\t\t***IMPLIMENTATION OF AVL TREE***\n\n");
while(1)
{
printf("1:insert\n");
printf("2:display\n");
printf("3:Exit\n");
printf("\tEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter the name : ");
scanf("%s",name);
if(search(root,name)==NULL)
root=insert(name,root,&htinc);
else
printf("Duplicate");
break;
case 2:
if(root==NULL)
{
printf("tree is empty");
continue;
}
printf("tree is :\n");
display(root,1);
printf("\n\n");
printf("in order traversal is: ");
inorder(root);
printf("\n");
break;
case 3:
exit(1);
default:
printf("wrong choice");
}
}
getch();
}

--------------------------------------------output----------------------------------------------
***IMPLIMENTATION OF AVL TREE***
1:insert
2:display
3:Exit
Enter your choice : 1
Enter the name : achu
1:insert
2:display
3:Exit
Enter your choice : 1
Enter the name : nisham
1:insert
2:display
3:Exit
Enter your choice : 1
Enter the name : rashi
RR rotation1:insert
2:display
3:Exit
Enter your choice : 1
Enter the name : abhi
1:insert
2:display
3:Exit
Enter your choice : 2
tree is :
rashi
nisham
achu
abhi
in order traversal is:
abhi
achu
nisham
rashi

1:insert
2:display
3:Exit
Enter your choice : 3