AVL_tree_and_its_operations.c

// C PROGRAM TO IMPLEMENT AVL TREE AND ITS OPERATIONS

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef enum { FALSE ,TRUE } bool;
struct node
{
    int info;
    int balance;
    struct node *lchild;
    struct node *rchild;
};
struct node *insert (int , struct node *, int *);
struct node* search(struct node *,int);
int inorder(struct node *);
int display(struct node *,int n);
void main()
{
    int ht_inc;
    int info ;
    int choice;
    struct node *root = (struct node *)malloc(sizeof(struct node));
    root = NULL;
    while(1)
    {
        printf("1.Insert\n");
        printf("2.Display\n");
        printf("3.Quit\n");
        printf("Enter your choice : ");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:
                printf("Enter the value to be inserted : ");
                scanf("%d", &info);
                if( search(root,info) == NULL )
                root = insert(info, root, &ht_inc);
                else
                printf("Duplicate value ignored\n");
                break;
            case 2:
                if(root==NULL)
                {
                printf("Tree is empty\n");
                continue;
                }
                printf("Tree is :\n");
                display(root, 1);
                printf("\n\n");
                printf("Inorder Traversal is: ");
                inorder(root);
                printf("\n");
                break;
            case 3:
                exit(1);
            default:
                printf("Wrong choice\n");
        }
    }
}
struct node* search(struct node *ptr,int info)
{
    if(ptr!=NULL)
    if(info < ptr->info)
    ptr=search(ptr->lchild,info);
    else if( info > ptr->info)
    ptr=search(ptr->rchild,info);
    return(ptr);
}/*End of search()*/
struct node *insert (int info, struct node *pptr, int *ht_inc)
{
    struct node *aptr;
    struct node *bptr;
    if(pptr==NULL)
    {
        pptr = (struct node *) malloc(sizeof(struct node));
        pptr->info = info;
        pptr->lchild = NULL;
        pptr->rchild = NULL;
        pptr->balance = 0;
        *ht_inc = TRUE;
        return (pptr);
    }
    if(info < pptr->info)
    {
        pptr->lchild = insert(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 = insert(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 insert()*/
int display(struct node *ptr,int level)
{
    int i;
    if ( ptr!=NULL )
    {
        display(ptr->rchild, level+1);
        printf("\n");
        for (i = 0; i < level; i++)
        printf(" ");
        printf("%d", ptr->info);
        display(ptr->lchild, level+1);
    }
    return(0);
}
int inorder(struct node *ptr)
{
    if(ptr!=NULL)
    {
        inorder(ptr->lchild);
        printf("%d ",ptr->info);
        inorder(ptr->rchild);
    }
    return(0);
}