平衡二叉树

  1 #include<time.h>
  2 #include<stdio.h>  
  3 #include<stdlib.h> 
  4 //左子树比右子树高一
  5 #define LH 1
  6 //左子树和右子树一样高
  7 #define EH 0
  8 //左子树比右子树低一
  9 #define RH -1
 10 #define EQ(a,b) ((a) == (b))
 11 #define LT(a,b) ((a) < (b))
 12 #define LQ(a,b)((a) <= (b))
 13 
 14 typedef struct BSTNode
 15 {
 16     int data;
 17     int bf;
 18     BSTNode * lchild;
 19     BSTNode * rchild;
 20 }BSTNode;
 21 typedef BSTNode * BSTree;
 22 
 23 //    左旋
 24 void leftRotate(BSTree & root) 
 25 {
 26     BSTree rc = root->rchild;
 27     root->rchild = rc->lchild;
 28     rc->lchild = root;
 29     root = rc;
 30 }
 31 //    右旋
 32 void rightRotate(BSTree & root) 
 33 {
 34     BSTree lc = root->lchild;
 35     root->lchild = lc->rchild;
 36     lc->rchild = root;
 37     root = lc;
 38 }
 39 //    对二叉树root进行左平衡处理(LL型和LR型)
 40 void leftBalance(BSTree & root) 
 41 {
 42     BSTree lc = root->lchild;
 43     switch (lc->bf) 
 44     {
 45         //LL型的只需要进行右旋操作
 46     case LH:
 47         //右旋之后根和左子树都的平衡的
 48         root->bf = EH;
 49         lc->bf = EH;
 50         //右旋操作
 51         rightRotate(root);
 52         break;
 53         //LR型的需要进行左旋操作，然后右旋操作
 54     case RH:
 55         BSTree rc = lc->rchild;
 56         switch (rc->bf) 
 57         {
 58         case LH:
 59             root->bf = RH;
 60             lc->bf = EH;
 61             break;
 62         case EH:
 63             root->bf = EH;
 64             lc->bf = EH;
 65             break;
 66         case RH:
 67             root->bf = EH;
 68             lc->bf = LH;
 69             break;
 70         }
 71         rc->bf = EH;
 72         leftRotate(root->lchild);
 73         rightRotate(root);
 74         break;
 75     }
 76 }
 77 //    功能：对二叉树root进行左平衡处理(RR型和RL型)
 78 void rightBalance(BSTree & root) 
 79 {
 80     BSTree rc = root->rchild;
 81     switch (rc->bf) 
 82     {
 83         //RR型只需要做左旋操作
 84     case RH:
 85         root->bf = EH;
 86         rc->bf = EH;
 87         //左旋操作
 88         leftRotate(root);
 89         break;
 90         //RL型需要先做右旋操作，然后做左旋操作
 91     case LH:
 92         BSTree lc = rc->lchild;
 93         switch (lc->bf) 
 94         {
 95         case LH:
 96             root->bf = EH;
 97             rc->bf = RH;
 98             break;
 99         case EH:
100             root->bf = EH;
101             rc->bf = EH;
102             break;
103         case RH:
104             root->bf = LH;
105             rc->bf = EH;
106             break;
107         }
108         lc->bf = EH;
109         rightRotate(root->rchild);
110         leftRotate(root);
111         break;
112     }
113 }
114 //    功能：把元素data插入平衡二叉树root中
115 bool insert(BSTree & root, int data, bool & taller) 
116 {
117     if (NULL == root) 
118     {
119         root = (BSTree)malloc(sizeof(BSTNode));
120         root->rchild = NULL;
121         root->lchild = NULL;
122         root->data = data;
123         root->bf = EH;
124         taller = true;
125     }
126     else
127     {
128         //该元素已经在平衡二叉树中存在了
129         if (data == root->data) 
130         {
131             taller = false;
132             return false;
133         }
134         //插入左子树
135         else if (data < root->data) 
136         {
137             if (!insert(root->lchild, data, taller)) 
138             {
139                 return false;
140             }
141             //插入成功，并且树变高了
142             if (taller) 
143             {
144                 switch (root->bf) 
145                 {
146                 case LH:
147                     leftBalance(root);
148                     //平衡二叉树做完左平衡操作后
149                     //树高没有变化，故taller = false
150                     taller = false;
151                     break;
152                 case EH:
153                     root->bf = LH;
154                     //原来是平衡的故插入一个元素后
155                     //树高必然变高
156                     taller = true;
157                     break;
158                 case RH:
159                     root->bf = EH;
160                     //原来是右子树比左子树高，但是当向左子树中
161                     //插入一个元素的时候，树变平衡了，故taller = false
162                     taller = false;
163                     break;
164                 default:
165                     break;
166                 }
167             }
168         }
169         //插入右子树
170         else 
171         {
172             if (!insert(root->rchild, data, taller)) 
173             {
174                 return 0;
175             }
176             if (taller) 
177             {
178                 switch (root->bf) 
179                 {
180                 case LH:
181                     root->bf = EH;
182                     taller = false;
183                     break;
184                 case EH:
185                     root->bf = RH;
186                     taller = true;
187                     break;
188                 case RH:
189                     rightBalance(root);
190                     taller = false;
191                     break;
192                 }
193             }
194         }
195     }
196     return true;
197 }
198 //   在平衡二叉树中查找int节点
199 int * search(BSTree & root, int data) 
200 {
201     if (root ==NULL) 
202     {
203         return NULL;
204     }
205     
206     if (root->data == data) 
207     {
208         return &root->data;
209     }
210     else if (data < root->data) 
211     {
212         return search(root->lchild, data);
213     } 
214     else 
215     {
216         return search(root->rchild, data);
217     }
218 }
219 //    功能：输出平衡二叉树中的所有的元素（小->大，中序遍历）
220 void print(BSTree & root)
221 {
222     if (NULL == root) 
223     {
224         return ;
225     }
226     
227     print(root->lchild);
228     printf("%d ",root->data);
229     print(root->rchild);
230 }
231 //    功能：释放平衡二叉树的空间
232 void clear(BSTree & root) 
233 {
234     if (NULL == root) 
235     {
236         return ;
237     }
238     clear(root->lchild);
239     clear(root->rchild);
240     free(root);
241 }
242 int DeleteAVL(BSTree &T, int key, bool &shorter){
243     if (!T)
244     {//No such key
245         shorter = false;
246         return 0;
247     }
248     else
249     {
250         if (EQ(key, T->data))    //找到了需要删除的结点
251         {
252             //如果该结点的lchild 和
253             //rchild 至少有一个为NULL
254             //则大功告成，否则请参照
255             //下方解释
256             BSTree q = T;
257             if (!T->lchild)//如果该结点的lchild 为NULL
258             {
259                 q = T;
260                 T = T->rchild;
261                 free(q);
262                 shorter = true;
263                 return 1;
264             }
265             else if (!T->rchild){//如果该结点的rchild 为 NULL
266                 q = T;
267                 T = T->lchild;//如果不是&（引用）的强大功能，这句话是没有意义的
268                 free(q);
269                 shorter = true;
270                 return 1;
271             }
272             else {
273                 //删除一个左右孩子都不为空的结点
274                 //使该结点的直接前驱p的data替换该结点的data
275                 //然后改变key=p.data
276                 BSTree s = T->lchild;
277                 while (s->rchild)
278                     s = s->rchild;
279                 T->data = s->data;
280                 key = s->data;//Now, delete the vertice whose data was the new key
281             }
282         }
283         if (LQ(key, T->data)){//这里与InsertAVL不同
284             if (!DeleteAVL(T->lchild, key, shorter)) return 0;
285             if (shorter){
286                 switch(T->bf){
287                 case LH:T->bf = EH; shorter = true;break;
288                 case EH:T->bf = RH;shorter = false;break;
289                 case RH:rightBalance(T); 
290                     if (T->rchild->bf == EH)
291                         shorter = false;
292                     else 
293                         shorter = true;break;
294                 }
295             }
296         }
297         else{
298             if (!DeleteAVL(T->rchild, key, shorter)) return 0;
299             if (shorter){
300                 switch(T->bf){
301                 case LH:leftBalance(T);
302                     if (T->lchild->bf == EH)
303                         shorter = false;
304                     else 
305                         shorter = true;break;
306                 case EH:T->bf = LH; shorter = false;break;
307                 case RH:T->bf = EH;shorter = true;break;
308                 }
309             }
310         }
311     }
312     return 1;
313 }//Delete
314 void menu()  
315 {  
316     printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙ ⊙☆⊙    主菜单     ⊙☆⊙ ⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n");  
317     printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙请按№ 1:连续插入数据 输入0结束插入⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n");  
318     printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙请按№ 2:查找数据                  ⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n");  
319     printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙请按№ 3删除特定数据               ⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n");  
320     printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙请按№ 4输出当前结果                   ⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n"); 
321     printf("⊙☆⊙ ⊙☆⊙ ⊙☆⊙请按№ 5结束程序                   ⊙☆⊙ ⊙☆⊙ ⊙☆⊙\n");
322 }  
323 int main()
324 {
325     BSTree root = NULL;
326     int num,n;
327     bool taller = false,shorter;
328     system("color 2e");  
329     menu();
330     while(1)  
331     {  
332         scanf("%d",&num); 
333         //if(num==5) break;
334         switch (num)  
335         {  
336         case 1:
337             system("cls");
338             printf("请插入数据 ，输入0结束插入\n");
339             while(scanf("%d",&n))
340             {
341                 if(n==0) break;
342                 else insert(root,n,taller);
343             }
344             system("cls");
345             menu();
346             break;
347         case 2: 
348             system("cls");
349             printf("请输入要查询的数\n");
350             scanf("%d",&n);
351             int *p;
352             p=search(root,n);
353             if (p==NULL) 
354             {
355                 printf("对不起 没有找到 %d!\n",n);
356             }
357             else 
358             {
359                 printf("恭喜你 数据中存在 %d!\n",n);
360             }
361             menu();
362             break;  
363         case 3: 
364             system("cls");
365             printf("请输入要删除的数据\n");
366             scanf("%d",&n);
367             DeleteAVL(root,n,shorter);
368             menu();
369             break;
370         case 4:
371             system("cls");
372             print(root); 
373             printf("输入0进入主菜单\n");
374             scanf("%d",&n);
375             if(!n)
376               menu();
377             break;
378         case 5:
379             clear(root);
380             return 0;        
381         }
382     }
383     return 0;
384 }
原文转自：http://blog.csdn.net/hnust_xiehonghao/article/details/7938869