C implementation of AVL tree

Implementation of AVL tree in C programming Language

# include<stdio.h>
# include<malloc.h>
# define F 0
# define T 1

struct NODE{        
    char Info;
    int Balance;
    struct  NODE *Left_Child;
    struct  NODE *Right_Child;
};

struct NODE *BINARY_TREE(int , struct NODE *, int *);
void OUTPUT(struct NODE *, int );
struct  NODE *BALANCE_RIGHT_HEAVY(struct NODE *, int *);
struct NODE *BALANCE_LEFT_HEAVY(struct NODE *, int *);
struct NODE *DELETE(struct NODE *, struct NODE *, int *);
struct NODE *DELETE_ELEMENT(struct NODE *, int , int *);
void INORDER(struct NODE*);
void PREORDER(struct NODE*);
void POSTORDER(struct NODE*);

/* Function main */

main(){
    int H;
    int Info ;
    int choice;
    struct NODE *Tree = (struct NODE *)malloc(sizeof(struct NODE));
    Tree = NULL;

//    printf("\n Input choice 'b' to break:");

    while(1){
        printf("\n1. INSERT\n");
        printf("2. DELETE\n");
        printf("3. DISPLAY INORDER\n");
        printf("4. DISPLAY PREORDER\n");
        printf("5. DISPLAY POSTORDER\n");
        printf("6. QUIT\n");
        printf("ENTER YOUR CHOICE : ");
        scanf("%d",&choice);

        switch(choice){
            case 1:
                printf("\n\n INPUT INFORMATION OF THE NODE: ");
                scanf("%d", &Info);
                Tree = BINARY_TREE(Info, Tree, &H);
                printf("\n TREE IS:\n");
                OUTPUT(Tree, 1);
                break;
            case 2:
                printf("\n INPUT THE KEY VALUE WANT TO DELETE :");
                scanf("%d", &Info);
                Tree = DELETE_ELEMENT(Tree, Info, &H);
                printf("\n TREE IS:\n");
                OUTPUT(Tree, 1);
                 break;
            case 3:
                 printf("THE IN-ORDER OF THE TREE IS:\n");
                 INORDER(Tree);
                 break;
               case 4:
                 printf("THE PRE-ORDER OF THE TREE IS:\n");
                 PREORDER(Tree);
                 break;
               case 5:
                 printf("THE POST-ORDER OF THE TREE IS:\n");
                 POSTORDER(Tree);
                 break;
            case 6:
                 exit(1);
         }
    }
}

/* Function to insert an element into tree */

struct NODE *BINARY_TREE(int Info, struct NODE *Parent, int *H){
    struct NODE *Node1;
    struct NODE *Node2;
    if(!Parent){
        Parent = (struct NODE *) malloc(sizeof(struct NODE));
        Parent->Info = Info;
        Parent->Left_Child = NULL;
        Parent->Right_Child = NULL;
        Parent->Balance = 0;
        *H = T;
        return (Parent);
    }

    if(Info < Parent->Info){
        Parent->Left_Child = BINARY_TREE(Info, Parent->Left_Child, H);
        if(*H)
        /* Left branch has grown higher */
        {
            switch(Parent->Balance){
                case 1: /* Right heavy */
                    Parent->Balance = 0;
                    *H = F;
                    break;
                case 0: /* Balanced tree */
                    Parent->Balance = -1;
                    break;
                case -1: /* Left heavy */
                    Node1 = Parent->Left_Child;
                    if(Node1->Balance == -1)
                    {
                        printf("\n LEFT TO LEFT ROTATION\n");
                        Parent->Left_Child= Node1->Right_Child;
                        Node1->Right_Child = Parent;
                        Parent->Balance = 0;
                        Parent = Node1;
                    }
                    else{
                        printf("\n LEFT TO RIGHT ROTATION\n");
                        Node2 = Node1->Right_Child;
                        Node1->Right_Child = Node2->Left_Child;
                        Node2->Left_Child = Node1;
                        Parent->Left_Child = Node2->Right_Child;
                        Node2->Right_Child = Parent;
                        if(Node2->Balance == -1)
                            Parent->Balance = 1;
                        else
                            Parent->Balance = 0;
                        if(Node2->Balance == 1)
                            Node1->Balance = -1;
                        else
                            Node1->Balance = 0;
                        Parent = Node2;
                    }
   
                    Parent->Balance = 0;
                    *H = F;
            }
        }
    }

    if(Info > Parent->Info){     
        Parent->Right_Child = BINARY_TREE(Info, Parent->Right_Child, H);
        if(*H)
        /* Right branch has grown higher */
        {
            switch(Parent->Balance){
                case -1: /* Left heavy */
                    Parent->Balance = 0;
                    *H = F;
                    break;
                case 0: /* Balanced tree */
                    Parent->Balance = 1;
                    break;
                case 1: /* Right heavy */
                    Node1 = Parent->Right_Child;
                    if(Node1->Balance == 1){
                        printf("\n RIGHT TO RIGHT ROTATION\n");
                        Parent->Right_Child= Node1->Left_Child;
                        Node1->Left_Child = Parent;
                        Parent->Balance = 0;
                        Parent = Node1;
            }
            else{
                printf("\n RIGHT TO RIGHT ROTATION\n");
                Node2 = Node1->Left_Child;
                Node1->Left_Child = Node2->Right_Child;
                Node2->Right_Child = Node1;
                Parent->Right_Child = Node2->Left_Child;
                Node2->Left_Child = Parent;

                if(Node2->Balance == 1)
                    Parent->Balance = -1;
                else
                    Parent->Balance = 0;
                if(Node2->Balance == -1)
                    Node1->Balance = 1;
                else
                    Node1->Balance = 0;
                    Parent = Node2;
            }

              Parent->Balance = 0;
            *H = F;
            }
        }
    }
    return(Parent);
}

/* Output function */

void OUTPUT(struct NODE *Tree,int Level){
    int i;
    if (Tree){
        OUTPUT(Tree->Right_Child, Level+1);
        printf("\n");
        for (i = 0; i < Level; i++)
            printf("   ");
        printf("%d", Tree->Info);
        OUTPUT(Tree->Left_Child, Level+1);
    }
}

/* Balancing Right Heavy */

struct NODE *BALANCE_RIGHT_HEAVY(struct NODE *Parent, int *H){
    struct NODE *Node1, *Node2;

    switch(Parent->Balance){
        case -1:
            Parent->Balance = 0;
            break;
        case 0:
            Parent->Balance = 1;
            *H= F;
            break;
        case 1: /* Rebalance */
            Node1 = Parent->Right_Child;
            if(Node1->Balance >= 0){
                printf("\n RIGHT TO RIGHT ROTATION\n");
                Parent->Right_Child= Node1->Left_Child;
                Node1->Left_Child = Parent;
                if(Node1->Balance == 0){
                    Parent->Balance = 1;
                    Node1->Balance = -1;
                    *H = F;
                }
                else{
                    Parent->Balance = Node1->Balance = 0;
                }
                Parent = Node1;
            }

            else{
                printf("\n RIGHT TO LEFT ROTATION\n");
                Node2 = Node1->Left_Child;
                Node1->Left_Child = Node2->Right_Child;
                Node2->Right_Child = Node1;
                Parent->Right_Child = Node2->Left_Child;
                Node2->Left_Child = Parent;
   
                if(Node2->Balance == 1)
                    Parent->Balance = -1;
                else
                    Parent->Balance = 0;
                if(Node2->Balance == -1)
                    Node1->Balance = 1;
                else
                    Node1->Balance = 0;
                Parent = Node2;
                Node2->Balance = 0;
            }
    }
    return(Parent);
}

/* Balancing Left Heavy */

struct NODE * BALANCE_LEFT_HEAVY(struct NODE *Parent, int *H){
    struct NODE *Node1, *Node2;

    switch(Parent->Balance){
        case 1:
            Parent->Balance = 0;
            break;
   
        case 0:
            Parent->Balance = -1;
            *H= F;
            break;
   
        case -1: /*  Rebalance */
            Node1 = Parent->Left_Child;
            if(Node1->Balance <= 0)
            {
                printf("\n LEFT TO LEFT ROTATION\n");
                Parent->Left_Child= Node1->Right_Child;
                Node1->Right_Child = Parent;
                if(Node1->Balance == 0)
                {
                    Parent->Balance = -1;
                    Node1->Balance = 1;
                    *H = F;
                }
                else
                {
                    Parent->Balance = Node1->Balance = 0;
                }
                Parent = Node1;
            }
            else
            {
                printf("\n LEFT TO RIGHT ROTATION\n");
                Node2 = Node1->Right_Child;
                Node1->Right_Child = Node2->Left_Child;
                Node2->Left_Child = Node1;
                Parent->Left_Child = Node2->Right_Child;
                Node2->Right_Child = Parent;
   
                if(Node2->Balance == -1)
                    Parent->Balance = 1;
                else
                    Parent->Balance = 0;
   
                if(Node2->Balance == 1)
                    Node1->Balance = -1;
                else
                    Node1->Balance = 0;
                Parent = Node2;
                Node2->Balance = 0;
            }
    }
    return(Parent);
}

/* Replace the node at which key is found with last right key of a left child */

struct NODE * DELETE(struct NODE *R, struct NODE *Temp, int *H){
    struct NODE *Dnode = R;
    if( R->Right_Child != NULL){
        R->Right_Child = DELETE(R->Right_Child, Temp, H);
        if(*H)
            R = BALANCE_LEFT_HEAVY(R, H);
    }
  
    else{
        Dnode = R;
        Temp->Info = R->Info;
        R = R->Left_Child;
        free(Dnode);
        *H = T;
    }
    return(R);
}
/* Delete the key element from the tree */

struct NODE * DELETE_ELEMENT(struct NODE *Parent, int Info, int *H){
    struct NODE *Temp;
    if(!Parent){
        printf("\n INFORMATION DOES NOT EXIST");                   
        return(Parent);
    }
  
    else{
        if (Info < Parent->Info ){
            Parent->Left_Child = DELETE_ELEMENT(Parent->Left_Child, Info, H);
            if(*H)
                Parent = BALANCE_RIGHT_HEAVY(Parent, H);
        }
        else if(Info > Parent->Info){
            Parent->Right_Child = DELETE_ELEMENT(Parent->Right_Child, Info, H);
            if(*H)
                Parent = BALANCE_LEFT_HEAVY(Parent, H);
        }
        else{
            Temp= Parent;
            if(Temp->Right_Child == NULL){
                Parent = Temp->Left_Child;
                *H = T;
                free(Temp);
            }
            else if(Temp->Left_Child == NULL){
                Parent = Temp->Right_Child;
                *H = T;
                free(Temp);
            }
            else{
                Temp->Left_Child = DELETE(Temp->Left_Child, Temp, H);
                if(*H)
                    Parent = BALANCE_RIGHT_HEAVY(Parent, H);
            }
        }
    }
    return(Parent);
}

void INORDER(struct NODE *Parent){
    if(Parent != NULL){
        INORDER(Parent->Left_Child);
        printf("\t%d",Parent->Info);
        INORDER(Parent->Right_Child);
    }
}

void PREORDER(struct NODE *Parent){
    if(Parent != NULL){
        printf("\t%d",Parent->Info);
        PREORDER(Parent->Left_Child);
        PREORDER(Parent->Right_Child);
    }
}

void POSTORDER(struct NODE *Parent){
    if(Parent != NULL){
        POSTORDER(Parent->Left_Child);
        POSTORDER(Parent->Right_Child);
        printf("\t%d",Parent->Info);
    }
}