8-6.c

这个是数据结构经典算法实现

#include "stdio.h"
typedef  struct info {
	int  key;
}element;
struct tree_node {
	struct tree_node *  left_child;
    element   data;
    short  int  bf;
    struct tree_node*  right_child;
};
typedef struct tree_node tree;
typedef  struct tree_node  *AVL_pt;
int IS_FULL(AVL_pt ptr)
{
	return (!ptr);
}
void left_rotation( AVL_pt parent , int *unbalanced )
{
        AVL_pt grand_child , child ; 
        child = parent->left_child ; 
        if ( child->bf == 1 ){
           /* LL 转置 */
           parent->left_child = child->right_child ; 
           child->right_child = parent ; 
           parent->bf = 0 ; 
           parent = child ; 
        }
        else {
        /* LR 转置 */
           grand_child = child->right_child ; 
           child->right_child = grand_child->left_child ; 
           grand_child->left_child = child ; 
           parent->left_child = grand_child->right_child ; 
           grand_child->right_child = parent ; 
           switch( grand_child->bf ){
                  case 1:  parent->bf = -1 ; 
                           child->bf = 0 ; 
                           break ; 
                  case 0:  parent->bf = child->bf = 0 ; 
                           break ; 
                  case -1: parent->bf = 0 ; 
                           child->bf = 1 ; 
           }
           parent = grand_child ; 
        }
        parent->bf=0; 
        *unbalanced=0 ; 
}       
void insert( AVL_pt parent , element x ,  int *unbalanced )
{  
	if ( !parent ){   /* 插入新元素 */
       *unbalanced = 1 ; 
       parent= (AVL_pt) malloc(sizeof(tree)) ; 
       if (IS_FULL(parent) ){
           printf("The memory is  full\n" ) ; 
           exit(1) ; 
       }
       parent->left_child = ( parent )->right_child = NULL ; 
       parent->bf = 0 ; 
       parent->data = x ; 
   }
   else if ( x.key < ( parent )->data.key ){
       insert(parent->left_child , x , unbalanced ) ; 
       if ( *unbalanced )
       /* 左支树高 */
          switch( ( parent )->bf ){
             case -1: ( parent )->bf = 0 ; 
                       *unbalanced = 0 ;     break ; 
             case 0:  ( parent )->bf = 1 ;        break ; 
             case 1:  left_rotation( parent , unbalanced ) ; 
          }
   }
   else if ( x.key > ( parent )->data.key ){
      insert(parent->right_child , x , unbalanced ) ; 
       if ( *unbalanced )
           /*右支树高*/
           switch ( parent->bf ){
              case 1:  parent->bf = 0 ; 
                       *unbalanced = 0 ;      break ; 
              case 0:  parent->bf = -1 ;       break ; 
              case -1:// right_rotation( parent , unbalanced ) 
				  ; 
           }
   }
   else {  *unbalanced = 0 ; 
       printf( "The key is already in the tree" ) ; 
   }
}
void main()
{
	int  unbalanced=0;
	element x;
	AVL_pt  root;
	x.key=10;
	root=NULL;
	insert (root, x, &unbalanced );
}