<![CDATA[
#include <stdio.h>
#include<malloc.h>
typedef enum{FALSE,TRUE}booleanx;
struct anode *avlinsert(int,struct anode*,booleanx*);
struct anode *avlsearch(struct anode*,int);
void avldisplay(struct anode*,int);
void avlinorder(struct anode*);
struct anode
{
int info; //data
int balance;//balance factor
struct anode *lchild;
struct anode *rchild;
};
void main()
{
booleanx ht_inc;
int info;
int choice;
system("cls");
struct anode *root=(struct anode*)malloc(sizeof(struct anode));
root=NULL;
while(1)
{
printf("\n1. Insert\n");
printf("\n2. Display\n");
printf("\n3. Return to tree menu\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter the value to be inserted:");
scanf("%d",&info);
if(avlsearch(root,info)==NULL)
root=avlinsert(info,root,&ht_inc);
else
printf("\n Duplicate value ignored\n");
break;
case 2:
if(root=NULL)
{
printf("\n Tree is empty\n");
continue;
}
printf("\n Tree is:\n");
avldisplay(root,1);
printf("\n\n");
printf("\n Inorder traversal is:");
avlinorder(root);
printf("\n");
break;
case 3:
return;
default : printf("\nWrong choice\n");
}//end of switch
}//end of while
}//end of main
struct anode *avlsearch(struct anode*ptr,int info)
{
if(ptr!=NULL)
if(info<ptr->info)
ptr=avlsearch(ptr->lchild,info);
else if(info>ptr->info)
ptr=avlsearch(ptr->rchild,info);
return ptr;
}//end of search
struct anode *avlinsert(int info,struct anode*pptr,booleanx*ht_inc)
{
struct anode *aptr;
struct anode *bptr;
if(pptr==NULL)
{
pptr=(struct anode*)malloc(sizeof(struct anode));
pptr->info=info;
pptr->lchild=NULL;
pptr->rchild=NULL;
pptr->balance=0
*ht_inc=true;
return pptr;
}
if (info<pptr->info)
{
pptr->lchild=avlinsert(info,pptr->lchild,ht_inc);
if(*ht_inc==true)
{
switch(pptr->balance)
{
case 1://right heavy;
pptr->balance=0
*ht_inc=false;
break;
case 0: //balanced
pptr->balance=1;
break;
case -1://left heavy
aptr=pptr->lchild;
if(aptr->balance==-1)
{
printf("left to left rotation\n");
pptr->lchild=aptr->rchild;
aptr->rchild=pptr;
pptr->balance=0;
aptr->balance=0;
pptr=aptr;
}
else
{
printf("left to right rotation\n");
bptr=aptr->rchild;
aptr->rchild=bptr->lchild;
bptr->lchild=aptr;
pptr->lchild=bptr->rchild;
bptr->rchild=pptr;
if (bptr->balance==1)
pptr->balance=-1;
else
pptr->balance=0;
if(bptr->balance==-1)
aptr->balance=1;
else
aptr->balance=0;
bptr->balance=0;
pptr=bptr;
}
*ht_inc=false;
}//end of switch
}//end of if
}//end of if
if(info>pptr->info)
{
pptr->rchild=avlinsert(info,pptr->rchild,ht_inc);
if (*ht_inc==true)
{
switch (pptr->balance)
{
case 1://left heavy
pptr->balance=0;
*ht_inc=false;
break;
case 0://balanced
pptr->balance=-1;
break;
case -1: //right heavy
aptr=pptr->rchild;
if (aptr->balance==-1)
{
printf("Right to right rotation\n");
pptr->rchild=aptr->lchild;
aptr->lchild=pptr;
pptr->balance=0;
aptr->balance=0;
pptr=aptr;
}
else
{
printf("Right to left rotation\n");
bptr=aptr->lchild;
aptr->lchild=bptr->rchild;
bptr->rchild=aptr;
pptr->rchild=bptr->lchild;
bptr->lchild=pptr;
if(bptr->balance==-1)
pptr->balance=1;
else
pptr->balance=0;
if(bptr->balance==1)
aptr->balance=-1;
else
aptr->balance=0;
bptr->balance=0;
pptr=bptr;
}//end of else
*ht_inc=false;
}//end of switch
}//end of if
}//end of if
return pptr;
}//end of the function
void avldisplay(struct anode*ptr,int level)
{
int i;
if (ptr!=NULL)
{
avldisplay(ptr->rchild,level+1);
printf("\n");
for (i=0; i<level;i++ )
printf(" "):
printf("%d",ptr->info);
avldisplay(ptr->lchild,level+1);
}//end of if
}//end of function
void avlinorder(struct anode*ptr)
{
if (ptr!=NULL)
{
avlinorder(ptr->lchild);
printf("%d",ptr->info);
avlinorder(ptr->rchild);
}
}
]]>
