1. #include "stdio.h"    
    2. #include "stdlib.h"   
    3. #include "io.h"  
    4. #include "math.h"  
    5. #include "time.h"
    7. #define OK 1
    8. #define ERROR 0
    9. #define TRUE 1
    10. #define FALSE 0
    11. #define MAXSIZE 100 /* 存储空间初始分配量 */
    13. typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 
    16. /* 二叉树的二叉链表结点结构定义 */
    17. typedef  struct BiTNode    /* 结点结构 */
    18. {
    19.     int data;    /* 结点数据 */
    20.     int bf; /*  结点的平衡因子 */ 
    21.     struct BiTNode *lchild, *rchild;    /* 左右孩子指针 */
    22. } BiTNode, *BiTree;
    25. /* 对以p为根的二叉排序树作右旋处理， */
    26. /* 处理之后p指向新的树根结点，即旋转处理之前的左子树的根结点 */
    27. void R_Rotate(BiTree *P)
    28. { 
    29.     BiTree L;
    30.     L=(*P)->lchild; /*  L指向P的左子树根结点 */ 
    31.     (*P)->lchild=L->rchild; /*  L的右子树挂接为P的左子树 */ 
    32.     L->rchild=(*P);
    33.     *P=L; /*  P指向新的根结点 */ 
    34. }
    36. /* 对以P为根的二叉排序树作左旋处理， */
    37. /* 处理之后P指向新的树根结点，即旋转处理之前的右子树的根结点0  */
    38. void L_Rotate(BiTree *P)
    39. { 
    40.     BiTree R;
    41.     R=(*P)->rchild; /*  R指向P的右子树根结点 */ 
    42.     (*P)->rchild=R->lchild; /* R的左子树挂接为P的右子树 */ 
    43.     R->lchild=(*P);
    44.     *P=R; /*  P指向新的根结点 */ 
    45. }
    47. #define LH +1 /*  左高 */ 
    48. #define EH 0  /*  等高 */ 
    49. #define RH -1 /*  右高 */ 
    51. /*  对以指针T所指结点为根的二叉树作左平衡旋转处理 */
    52. /*  本算法结束时，指针T指向新的根结点 */
    53. void LeftBalance(BiTree *T)
    54. { 
    55.     BiTree L,Lr;
    56.     L=(*T)->lchild; /*  L指向T的左子树根结点 */ 
    57.     switch(L->bf)
    58.     { /*  检查T的左子树的平衡度，并作相应平衡处理 */ 
    59.          case LH: /*  新结点插入在T的左孩子的左子树上，要作单右旋处理 */ 
    60.             (*T)->bf=L->bf=EH;
    61.             R_Rotate(T);
    62.             break;
    63.          case RH: /*  新结点插入在T的左孩子的右子树上，要作双旋处理 */ 
    64.             Lr=L->rchild; /*  Lr指向T的左孩子的右子树根 */ 
    65.             switch(Lr->bf)
    66.             { /*  修改T及其左孩子的平衡因子 */ 
    67.                 case LH: (*T)->bf=RH;
    68.                          L->bf=EH;
    69.                          break;
    70.                 case EH: (*T)->bf=L->bf=EH;
    71.                          break;
    72.                 case RH: (*T)->bf=EH;
    73.                          L->bf=LH;
    74.                          break;
    75.             }
    76.             Lr->bf=EH;
    77.             L_Rotate(&(*T)->lchild); /*  对T的左子树作左旋平衡处理 */ 
    78.             R_Rotate(T); /*  对T作右旋平衡处理 */ 
    79.     }
    80. }
    82. /*  对以指针T所指结点为根的二叉树作右平衡旋转处理， */ 
    83. /*  本算法结束时，指针T指向新的根结点 */ 
    84. void RightBalance(BiTree *T)
    85. { 
    86.     BiTree R,Rl;
    87.     R=(*T)->rchild; /*  R指向T的右子树根结点 */ 
    88.     switch(R->bf)
    89.     { /*  检查T的右子树的平衡度，并作相应平衡处理 */ 
    90.      case RH: /*  新结点插入在T的右孩子的右子树上，要作单左旋处理 */ 
    91.               (*T)->bf=R->bf=EH;
    92.               L_Rotate(T);
    93.               break;
    94.      case LH: /*  新结点插入在T的右孩子的左子树上，要作双旋处理 */ 
    95.               Rl=R->lchild; /*  Rl指向T的右孩子的左子树根 */ 
    96.               switch(Rl->bf)
    97.               { /*  修改T及其右孩子的平衡因子 */ 
    98.                 case RH: (*T)->bf=LH;
    99.                          R->bf=EH;
    100.                          break;
    101.                 case EH: (*T)->bf=R->bf=EH;
    102.                          break;
    103.                 case LH: (*T)->bf=EH;
    104.                          R->bf=RH;
    105.                          break;
    106.               }
    107.               Rl->bf=EH;
    108.               R_Rotate(&(*T)->rchild); /*  对T的右子树作右旋平衡处理 */ 
    109.               L_Rotate(T); /*  对T作左旋平衡处理 */ 
    110.     }
    111. }
    113. /*  若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */ 
    114. /*  数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */ 
    115. /*  失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。 */
    116. Status InsertAVL(BiTree *T,int e,Status *taller)
    117. {  
    118.     if(!*T)
    119.     { /*  插入新结点，树“长高”，置taller为TRUE */ 
    120.          *T=(BiTree)malloc(sizeof(BiTNode));
    121.          (*T)->data=e; (*T)->lchild=(*T)->rchild=NULL; (*T)->bf=EH;
    122.          *taller=TRUE;
    123.     }
    124.     else
    125.     {
    126.         if (e==(*T)->data)
    127.         { /*  树中已存在和e有相同关键字的结点则不再插入 */ 
    128.             *taller=FALSE; return FALSE;
    129.         }
    130.         if (e<(*T)->data)
    131.         { /*  应继续在T的左子树中进行搜索 */ 
    132.             if(!InsertAVL(&(*T)->lchild,e,taller)) /*  未插入 */ 
    133.                 return FALSE;
    134.             if(*taller) /*   已插入到T的左子树中且左子树“长高” */ 
    135.                 switch((*T)->bf) /*  检查T的平衡度 */ 
    136.                 {
    137.                     case LH: /*  原本左子树比右子树高，需要作左平衡处理 */ 
    138.                             LeftBalance(T);    *taller=FALSE; break;
    139.                     case EH: /*  原本左、右子树等高，现因左子树增高而使树增高 */ 
    140.                             (*T)->bf=LH; *taller=TRUE; break;
    141.                     case RH: /*  原本右子树比左子树高，现左、右子树等高 */  
    142.                             (*T)->bf=EH; *taller=FALSE; break;
    143.                 }
    144.         }
    145.         else
    146.         { /*  应继续在T的右子树中进行搜索 */ 
    147.             if(!InsertAVL(&(*T)->rchild,e,taller)) /*  未插入 */ 
    148.                 return FALSE;
    149.             if(*taller) /*  已插入到T的右子树且右子树“长高” */ 
    150.                 switch((*T)->bf) /*  检查T的平衡度 */ 
    151.                 {
    152.                     case LH: /*  原本左子树比右子树高，现左、右子树等高 */ 
    153.                             (*T)->bf=EH; *taller=FALSE;    break;
    154.                     case EH: /*  原本左、右子树等高，现因右子树增高而使树增高  */
    155.                             (*T)->bf=RH; *taller=TRUE; break;
    156.                     case RH: /*  原本右子树比左子树高，需要作右平衡处理 */ 
    157.                             RightBalance(T); *taller=FALSE; break;
    158.                 }
    159.         }
    160.     }
    161.     return TRUE;
    162. }
    164. int main(void)
    165. {    
    166.     int i;
    167.     int a[10]={3,2,1,4,5,6,7,10,9,8};
    168.     BiTree T=NULL;
    169.     Status taller;
    170.     for(i=0;i<10;i++)
    171.     {
    172.         InsertAVL(&T,a[i],&taller);
    173.     }
    174.     printf("本样例建议断点跟踪查看平衡二叉树结构");
    175.     return 0;
    176. }