AVL Tree in C language

AVL Tree in C language

Use C programming language to make an AVL tree and display the tree in INORDER formate.

Code

/******AVL tree******/
#include <stdio.h>
#include <stdlib.h>

//Structure for tree
struct AVL 
{
 int data,height;
 struct AVL *left,*right;
};

//Function definition for getting maximum value
int max(int a,int b)
{
 if(a>=b)
  return a;
 else
  return b; 
}

//Function definition for getting the height of the tree
int height(struct AVL **root)
{
 if(*root==NULL)
  return 0;
 return (*root)->height; 
}

//Function definition for getting the balance factor of the tree
int balance(struct AVL **root)
{
 return(height(&((*root)->left))-height(&((*root)->right)));
}

//Function definition for rotate the tree right
void rightrotate(struct AVL **root)
{
 struct AVL *child,*temp;
 child=(*root)->left;
 temp=child->right;
 child->right=*root;
 (*root)->left=temp;
 (*root)->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
 child->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
 *root= child;
 
}

//Function definition for rotate the tree left
void leftrotate(struct AVL **root)
{
 struct AVL *child,*temp;
 child=(*root)->right;
 temp=child->left;
 child->left=*root;
 (*root)->right=temp;
 (*root)->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
 child->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;
  *root=child;
}

//Function definition for creating
void create(struct AVL **root,int d)
{  int bal;
 if(*root==NULL)
 {
   *root=(struct AVL*)malloc(sizeof(struct AVL));
   (*root)->data=d;
   (*root)->height=1;
   (*root)->left=NULL;
   (*root)->right=NULL;
   return; 
 }
 else if(d > (*root)->data)
  create(&((*root)->right),d);
 else if(d < (*root)->data)
  create(&((*root)->left),d);
 else
   printf("item already exist");
 (*root)->height=max(height(&((*root)->left)),height(&((*root)->right)))+1;  
 bal=balance(&(*root));
 if(bal< -1 && d < (*root)->right->data)
 {
  rightrotate(&((*root)->right));
  leftrotate(&(*root));
 }
 if(bal > 1 && d < (*root)->left->data)
  rightrotate(&(*root)); 
 if(bal < -1 && d < (*root)->right->data)
 {
  leftrotate(&(*root));
 }
 if(bal > 1 && d > (*root)->left->data)
 {
  leftrotate(&((*root)->left));
  rightrotate(&(*root));
 }
    
}

//Function definition for inorder traversal
void inorder(struct AVL **root)
{
 if(*root)
 {
  inorder(&((*root)->left));
  printf("%d\t",(*root)->data);
  inorder(&((*root)->right));
 }
}
int main()
{
 struct AVL *root=NULL;
 int ch,d;
 do
 {   
  printf("\n1.create or insert element to AVL tree");
  printf("\n2.inorder display element to tree");
  printf("\n3.exit");
  printf("\nenter ur choice");
  scanf("%d",&ch);
  switch (ch)
  {
   case 1:
    printf("\nenter element to new node");
    scanf("%d",&d);
    create(&root,d);
    break;
   case 2:
    inorder(&root);
    getch();
    break;
   case 3:
    exit(0);
   default:
    printf("invalid choice");   
  }
 }while(1);
 return (0); 
}

Output

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node10

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node5

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node15

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node3

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node2

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice1

enter element to new node6

1.create or insert element to   AVL tree
2.inorder display element to tree
3.exit
enter ur choice2
2       3       5       6       10      15