C-program for balanced trees(AVL Trees)Inorder traversal using right rotations(LL) left rotations(RR) and (RL

data structures - tree traversal- request for full C-program to realize balanced trees

C-program for balanced trees(AVL Trees)Inorder traversal using right rotations(LL) left rotations(RR) and (RL
/* Program to maintain an AVL tree. */





#include %26lt;stdio.h%26gt;


#include %26lt;conio.h%26gt;


#include %26lt;alloc.h%26gt;





#define FALSE 0


#define TRUE 1





struct AVLNode


{


int data ;


int balfact ;


struct AVLNode *left ;


struct AVLNode *right ;


} ;





struct AVLNode * buildtree ( struct AVLNode *, int, int * ) ;


struct AVLNode * deldata ( struct AVLNode *, int, int * ) ;


struct AVLNode * del ( struct AVLNode *, struct AVLNode *, int * ) ;


struct AVLNode * balright ( struct AVLNode *, int * ) ;


struct AVLNode * balleft ( struct AVLNode *, int * ) ;


void display ( struct AVLNode * ) ;


void deltree ( struct AVLNode * ) ;





void main( )


{


struct AVLNode *avl = NULL ;


int h ;





clrscr( ) ;





avl = buildtree ( avl, 20, %26amp;h ) ;


avl = buildtree ( avl, 6, %26amp;h ) ;


avl = buildtree ( avl, 29, %26amp;h ) ;


avl = buildtree ( avl, 5, %26amp;h ) ;


avl = buildtree ( avl, 12, %26amp;h ) ;


avl = buildtree ( avl, 25, %26amp;h ) ;


avl = buildtree ( avl, 32, %26amp;h ) ;


avl = buildtree ( avl, 10, %26amp;h ) ;


avl = buildtree ( avl, 15, %26amp;h ) ;


avl = buildtree ( avl, 27, %26amp;h ) ;


avl = buildtree ( avl, 13, %26amp;h ) ;





printf ( "\nAVL tree:\n" ) ;


display ( avl ) ;





avl = deldata ( avl, 20, %26amp;h ) ;


avl = deldata ( avl, 12, %26amp;h ) ;





printf ( "\nAVL tree after deletion of a node:\n" ) ;


display ( avl ) ;





deltree ( avl ) ;





getch( ) ;


}





/* inserts an element into tree */


struct AVLNode * buildtree ( struct AVLNode *root, int data, int *h )


{


struct AVLNode *node1, *node2 ;





if ( !root )


{


root = ( struct AVLNode * ) malloc ( sizeof ( struct AVLNode ) ) ;


root -%26gt; data = data ;


root -%26gt; left = NULL ;


root -%26gt; right = NULL ;


root -%26gt; balfact = 0 ;


*h = TRUE ;


return ( root ) ;


}





if ( data %26lt; root -%26gt; data )


{


root -%26gt; left = buildtree ( root -%26gt; left, data, h ) ;


/* If left subtree is higher */


if ( *h )


{


switch ( root -%26gt; balfact )


{


case 1:


node1 = root -%26gt; left ;


if ( node1 -%26gt; balfact == 1 )


{


printf ( "\nRight rotation along %d.", root -%26gt; data ) ;


root -%26gt; left = node1 -%26gt; right ;


node1 -%26gt; right = root ;


root -%26gt; balfact = 0 ;


root = node1 ;


}


else


{


printf ( "\nDouble rotation, left along %d",


node1 -%26gt; data ) ;


node2 = node1 -%26gt; right ;


node1 -%26gt; right = node2 -%26gt; left ;


printf ( " then right along %d.\n", root -%26gt; data ) ;


node2 -%26gt; left = node1 ;


root -%26gt; left = node2 -%26gt; right ;


node2 -%26gt; right = root ;


if ( node2 -%26gt; balfact == 1 )


root -%26gt; balfact = -1 ;


else


root -%26gt; balfact = 0 ;


if ( node2 -%26gt; balfact == -1 )


node1 -%26gt; balfact = 1 ;


else


node1 -%26gt; balfact = 0 ;


root = node2 ;


}


root -%26gt; balfact = 0 ;


*h = FALSE ;


break ;





case 0:


root -%26gt; balfact = 1 ;


break ;





case -1:


root -%26gt; balfact = 0 ;


*h = FALSE ;


}


}


}





if ( data %26gt; root -%26gt; data )


{


root -%26gt; right = buildtree ( root -%26gt; right, data, h ) ;


/* If the right subtree is higher */


if ( *h )


{


switch ( root -%26gt; balfact )


{


case 1:


root -%26gt; balfact = 0 ;


*h = FALSE ;


break ;





case 0:


root -%26gt; balfact = -1 ;


break;





case -1:


node1 = root -%26gt; right ;


if ( node1 -%26gt; balfact == -1 )


{


printf ( "\nLeft rotation along %d.", root -%26gt; data ) ;


root -%26gt; right = node1 -%26gt; left ;


node1 -%26gt; left = root ;


root -%26gt; balfact = 0 ;


root = node1 ;


}


else


{


printf ( "\nDouble rotation, right along %d",


node1 -%26gt; data ) ;


node2 = node1 -%26gt; left ;


node1 -%26gt; left = node2 -%26gt; right ;


node2 -%26gt; right = node1 ;


printf ( " then left along %d.\n", root -%26gt; data ) ;


root -%26gt; right = node2 -%26gt; left ;


node2 -%26gt; left = root ;





if ( node2 -%26gt; balfact == -1 )


root -%26gt; balfact = 1 ;


else


root -%26gt; balfact = 0 ;


if ( node2 -%26gt; balfact == 1 )


node1 -%26gt; balfact = -1 ;


else


node1 -%26gt; balfact = 0 ;


root = node2 ;


}


root -%26gt; balfact = 0 ;


*h = FALSE ;


}


}


}


return ( root ) ;


}





/* deletes an item from the tree */


struct AVLNode * deldata ( struct AVLNode *root, int data, int *h )


{


struct AVLNode *node ;





if ( !root )


{


printf ( "\nNo such data." ) ;


return ( root ) ;


}


else


{


if ( data %26lt; root -%26gt; data )


{


root -%26gt; left = deldata ( root -%26gt; left, data, h ) ;


if ( *h )


root = balright ( root, h ) ;


}


else


{


if ( data %26gt; root -%26gt; data )


{


root -%26gt; right = deldata ( root -%26gt; right, data, h ) ;


if ( *h )


root = balleft ( root, h ) ;


}


else


{


node = root ;


if ( node -%26gt; right == NULL )


{


root = node -%26gt; left ;


*h = TRUE ;


free ( node ) ;


}


else


{


if ( node -%26gt; left == NULL )


{


root = node -%26gt; right ;


*h = TRUE ;


free ( node ) ;


}


else


{


node -%26gt; right = del ( node -%26gt; right, node, h ) ;


if ( *h )


root = balleft ( root, h ) ;


}


}


}


}


}


return ( root ) ;


}





struct AVLNode * del ( struct AVLNode *succ, struct AVLNode *node, int *h )


{


struct AVLNode *temp = succ ;


if ( succ -%26gt; left != NULL )


{


succ -%26gt; left = del ( succ -%26gt; left, node, h ) ;


if ( *h )


succ = balright ( succ, h ) ;


}


else


{


temp = succ ;


node -%26gt; data = succ -%26gt; data ;


succ = succ -%26gt; right ;


free ( temp ) ;


*h = TRUE ;


}


return ( succ ) ;


}





/* balances the tree, if right sub-tree is higher */


struct AVLNode * balright ( struct AVLNode *root, int *h )


{


struct AVLNode *node1, *node2 ;





switch ( root -%26gt; balfact )


{


case 1:


root -%26gt; balfact = 0 ;


break;





case 0:


root -%26gt; balfact = -1 ;


*h = FALSE ;


break;





case -1:


node1 = root -%26gt; right ;


if ( node1 -%26gt; balfact %26lt;= 0 )


{


printf ( "\nLeft rotation along %d.", root -%26gt; data ) ;


root -%26gt; right = node1 -%26gt; left ;


node1 -%26gt; left = root ;


if ( node1 -%26gt; balfact == 0 )


{


root -%26gt; balfact = -1 ;


node1 -%26gt; balfact = 1 ;


*h = FALSE ;


}


else


{


root -%26gt; balfact = node1 -%26gt; balfact = 0 ;


}


root = node1 ;


}


else


{


printf ( "\nDouble rotation, right along %d", node1 -%26gt; data );


node2 = node1 -%26gt; left ;


node1 -%26gt; left = node2 -%26gt; right ;


node2 -%26gt; right = node1 ;


printf ( " then left along %d.\n", root -%26gt; data );


root -%26gt; right = node2 -%26gt; left ;


node2 -%26gt; left = root ;





if ( node2 -%26gt; balfact == -1 )


root -%26gt; balfact = 1 ;


else


root -%26gt; balfact = 0 ;


if ( node2 -%26gt; balfact == 1 )


node1 -%26gt; balfact = -1 ;


else


node1 -%26gt; balfact = 0 ;


root = node2 ;


node2 -%26gt; balfact = 0 ;


}


}


return ( root ) ;


}





/* balances the tree, if left sub-tree is higher */


struct AVLNode * balleft ( struct AVLNode *root, int *h )


{


struct AVLNode *node1, *node2 ;





switch ( root -%26gt; balfact )


{


case -1:


root -%26gt; balfact = 0 ;


break ;





case 0:


root -%26gt; balfact = 1 ;


*h = FALSE ;


break ;





case 1:


node1 = root -%26gt; left ;


if ( node1 -%26gt; balfact %26gt;= 0 )


{


printf ( "\nRight rotation along %d.", root -%26gt; data ) ;


root -%26gt; left = node1 -%26gt; right ;


node1 -%26gt; right = root ;


if ( node1 -%26gt; balfact == 0 )


{


root -%26gt; balfact = 1 ;


node1 -%26gt; balfact = -1 ;


*h = FALSE ;


}


else


{


root -%26gt; balfact = node1 -%26gt; balfact = 0 ;


}


root = node1 ;


}


else


{


printf ( "\nDouble rotation, left along %d", node1 -%26gt; data ) ;


node2 = node1 -%26gt; right ;


node1 -%26gt; right = node2 -%26gt; left ;


node2 -%26gt; left = node1 ;


printf ( " then right along %d.\n", root -%26gt; data ) ;


root -%26gt; left = node2 -%26gt; right ;


node2 -%26gt; right = root ;





if ( node2 -%26gt; balfact == 1 )


root -%26gt; balfact = -1 ;


else


root -%26gt; balfact = 0 ;


if ( node2-%26gt; balfact == -1 )


node1 -%26gt; balfact = 1 ;


else


node1 -%26gt; balfact = 0 ;


root = node2 ;


node2 -%26gt; balfact = 0 ;


}


}


return ( root ) ;


}





/* displays the tree in-order */


void display ( struct AVLNode *root )


{


if ( root != NULL )


{


display ( root -%26gt; left ) ;


printf ( "%d\t", root -%26gt; data ) ;


display ( root -%26gt; right ) ;


}


}





/* deletes the tree */


void deltree ( struct AVLNode *root )


{


if ( root != NULL )


{


deltree ( root -%26gt; left ) ;


deltree ( root -%26gt; right ) ;


}


free ( root ) ;


}
Reply:For a balanced tree, number of apples on the left branch must equal to the number of apples on the right branch. This is the whole story.