1 #include 
     
         2 #include 
      
          3 #define FALSE 0   4 #define TRUE 1   5 char chos;   6 int input;   7   8 struct node{
     9     int data;  10     int bf;  11     struct node *lchild;  12     struct node *rchild;  13 };  14  15 typedef struct node *BST;  16 BST R = NULL;  17  18 void chose()  19 {
    20     printf("i) Insert a point \n"  21            "d) Delete a point \n"  22            "e) exit\n"  23            "Input your choose:");  24     scanf("%c", &chos);  25 }  26  27 int Height(BST T)  28 {
    29     if(T == NULL)  30       return -1;  31     else  32       return T->bf;  33 }  34  35 int Max(int a, int b)  36 {
    37     return (a > b ? a : b);  38 }  39  40 /*RR旋转*/  41 /* k1指向k2的右子树，沿着k2旋转，使得k1成为根节点，并返回k1*/  42 BST SingleRotatewithRight(BST k2)  43 {
    44     BST k1;  45     k1 = k2->rchild;  46     k2->rchild = k1->lchild;  47     k1->lchild = k2;  48     k2->bf = Max(Height(k2->lchild), Height(k2->rchild));  49     k1->bf = Max(Height(k1->lchild), Height(k1->rchild));  50     return k1;  51 }  52  53 /*LL旋转 */  54 /**/  55 BST SingleRotatewithLeft(BST k2)  56 {
    57     BST k1;  58     k1 = k2->lchild;  59     k2->lchild = k1->rchild;  60     k1->rchild = k2;  61     k2->bf = Max(Height(k2->lchild), Height(k2->rchild));  62     k1->bf = Max(Height(k1->lchild), Height(k1->rchild));  63     return k1;  64 }  65  66 /* LR旋转 */  67 /**/  68 BST DoubleRotatewithLeft(BST k3)  69 {
    70     k3->lchild = SingleRotatewithRight(k3->lchild);  71     return SingleRotatewithLeft(k3);  72 }  73  74 /* RL旋转 */  75 BST DoubleRotatewithRight(BST k3)  76 {
    77     k3->rchild = SingleRotatewithLeft(k3->rchild);  78     return SingleRotatewithRight(k3);  79 }  80  81 void OUT(BST T)  82 {
    83     if(T->lchild)  84     {
    85         printf("Left\t%d[parent:%d]\n", T->lchild->data, T->data);  86         OUT(T->lchild);  87     }  88     if(T->rchild)  89     {
    90         printf("Right\t%d[parent:%d]\n", T->rchild->data, T->data);  91         OUT(T->rchild);  92     }  93 }  94  95 /* 调整单个节点，在此定义平衡因子为 Height(lchile) - Height(rchild) */  96 /**/  97 BST Rotate(BST T)  98 {
    99     if(Height(T->lchild) - Height(T->rchild) == 2) 100     {
   101         if(Height(T->lchild->lchild) >= Height(T->lchild->rchild)) 102           T = SingleRotatewithLeft(T); 103         else 104           T = DoubleRotatewithLeft(T); 105     } 106     if(Height(T->rchild) - Height(T->lchild) == 2) 107     {
   108         if(Height(T->rchild->rchild) >= Height(T->rchild->lchild)) 109           T = SingleRotatewithRight(T); 110         else 111           T = DoubleRotatewithRight(T); 112     } 113     return T; 114 } 115 116 BST AVLInsert(BST T) 117 {
   118     if(T == NULL) 119     {
   /* 若二叉树为空，则创建二叉树 */ 120         T  = (BST)malloc(sizeof(struct node)); 121         if(T == NULL) 122         {
   123             perror("malloc"); 124             exit(-1); 125         } 126         T->data = input; 127         T->lchild = NULL; 128         T->rchild = NULL; 129         T->bf = 0; 130     } 131     else if(input < T->data) 132     {
   /* 将节点插入左子树中，采用递归 */ 133         T->lchild = AVLInsert(T->lchild); 134         if(Height(T->lchild) - Height(T->rchild) == 2) 135         {
   136             if(input < T->lchild->data) 137               T = SingleRotatewithLeft(T); 138             else 139               T = SingleRotatewithLeft(T); 140         } 141     } 142     else if(input > T->data) 143     {
   144         T->rchild = AVLInsert(T->rchild); 145         if(Height(T->rchild) - Height(T->lchild) == 2) 146         {
   147             if(input > T->rchild->data) 148               T = SingleRotatewithRight(T); 149             else 150               T = DoubleRotatewithRight(T); 151         } 152     } 153     T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1; 154     return T; 155 } 156 157 158 void output(BST T) 159 {
   160     if(T == NULL) 161       printf("None\n"); 162     else 163     {
   164         printf("%d\troot\n", T->data); 165         OUT(T); 166     } 167 } 168 169 170 void Insert() 171 {
   172     printf("\nInput the point your want to Insert:"); 173     scanf("%d", &input); 174     R = AVLInsert(R); 175     output(R); 176 } 177 178 179 BST AVLDelete(BST T, int key) 180 {
   181     if(T == NULL)    182       return NULL; 183     if(key == T->data) 184     {
   185         if(T->rchild == NULL) 186         {
   187             BST tmp = T; 188             T = T->lchild; 189             free(tmp); 190         } 191         else 192         {
   /* 选择右子树最左节点作为新二叉树的根节点,并将这个最左节点删除 */ 193             BST tmp = T->rchild; 194             while(tmp->lchild != NULL) 195               tmp = tmp->lchild; 196             T->data = tmp->data; 197             T->rchild = AVLDelete(T->rchild, tmp->data); 198             T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1; 199         } 200         return T; 201     } 202     else if(key < T->data) 203     {
   204         T->lchild = AVLDelete(T->lchild, key); 205     } 206     else 207     {
   208         T->rchild = AVLDelete(T->rchild, key); 209     } 210     T->bf = Max(Height(T->lchild), Height(T->rchild)) + 1; 211     if(T->lchild != NULL) 212       T->lchild = Rotate(T->lchild); 213     if(T->rchild != NULL) 214       T->rchild = Rotate(T->rchild); 215     T = Rotate(T); 216     return T; 217 } 218 219 void Delete() 220 {
   221     printf("\nInput the point you want to Delete: "); 222     scanf("%d", &input); 223     R = AVLDelete(R, input); 224     output(R); 225 } 226 227 int main() 228 {
   229     while(1) 230     {
   231         chose(); 232         switch(chos) 233         {
   234             case 'i': 235                 Insert(); 236                 break; 237             case 'd': 238                 Delete(); 239                 break; 240             case 'e': 241                 exit(0); 242         } 243     } 244     return 0; 245 }