关于平衡二叉树完整算法实现(部分修改)

零度非安全

哈喽，各位鱼油们你们好，由于最近在忙各种课程作业，所以很少上论坛，今天有幸跟各位鱼油来分享下关于平衡二叉树算法的实现

早在之前，小甲鱼老师已经在《数据结构与算法》中提到了关于平衡二叉树的讲解，当时我也看的稀里糊涂的，完全不知道他在讲什么？但是这个学期我们也在学这门课程，所以呢，我花了几天的时间写了个关于平衡二叉树的算法，个人觉得还算可以，如果有谁看了我写的算法后，觉得某些地方需要改动的话，请跟帖回复

如果有人提出较好的意见的，我会给额外的奖励滴
代码共计478行，代码如下：

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<malloc.h>
   
4. #define MaxSize 100
   
5. #define MaxWith 50
   
6. 
   
7. typedef int KeyType;
   
8. typedef char InfoType;
   
9. 
   
10. /*定义各节点的类型*/
    
11. typedef struct node
    
12. {
    
13.         KeyType key;                                                                                                                        /*关键字项*/
    
14.         int bf;                                                                                                                                        /*增加的平衡因子*/
    
15.         InfoType data;                                                                                                                        /*其它的数据与域*/
    
16.         struct node *lchild;                                                                                                        /*左孩子指针*/
    
17.         struct node *rchild;                                                                                                        /*右孩子指针*/
    
18. }AVLNode;                                                                                                                                        /*AVL树中节点类型定义*/
    
19. 
    
20. int m = 0;
    
21. AVLNode *b = NULL;                                                                                                                        /*定义全局变量m、*b*/
    
22. 
    
23. /*左平衡旋转情况处理*/
    
24. void LeftProcess(AVLNode *&p, int &taller)
    
25. {
    
26.         AVLNode *p1, *p2;
    
27.         if (p->bf == 0)                                                                                                                        /*当左右子树等高时插入使树高度增加*/
    
28.         {
    
29.                 p->bf = 1;
    
30.                 taller = 1;                                                                                                                        /*所以平衡因子置为1，高度为1*/
    
31.         }
    
32.         else if (p->bf == -1)                                                                                                        /*当右子树比左子树高，插入后左右子树等高*/
    
33.         {
    
34.                 p->bf = 0;
    
35.                 taller = 0;                                                                                                                        /*所以平衡因子置为0，高度为0*/
    
36.         }
    
37.         else                                                                                                                                        /*当左子树比右子树高时插入则需做左平衡处理*/
    
38.         {
    
39.                 p1 = p->lchild;
    
40.                 if (p1->bf == 1)                                                                                                        /*当插入到左孩子的左子树上时需做LL处理*/
    
41.                 {
    
42.                         p->lchild = p1->rchild;
    
43.                         p1->rchild = p;
    
44.                         p->bf = p1->bf = 0;
    
45.                         p = p1;
    
46.                 }
    
47.                 else if (p1->bf == -1)                                                                                                /*当插入到左孩子的右子树上时需做LR处理*/
    
48.                 {
    
49.                         p2 = p1->rchild;
    
50.                         p1->rchild = p2->lchild;
    
51.                         p2->lchild = p1;
    
52.                         p->lchild = p2->rchild;
    
53.                         p2->rchild = p;
    
54.                         p = p2;                                                                                                                        /*将p指向新的根节点，并置bf的值为0*/
    
55.                         p->bf = 0;
    
56.                 }
    
57.                 taller = 0;
    
58.         }
    
59. }
    
60. 
    
61. /*右平衡旋转情况处理*/
    
62. void RightProcess(AVLNode *&p, int &taller)                                                                        /*操作类似上面，请参照左平衡旋转处理*/
    
63. {
    
64.         AVLNode *p1, *p2;
    
65.         if (p->bf == 0)
    
66.         {
    
67.                 p->bf = -1;
    
68.                 taller = 1;
    
69.         }
    
70.         else if (p->bf == 1)
    
71.         {
    
72.                 p->bf = 0;
    
73.                 taller = 0;
    
74.         }
    
75.         else
    
76.         {
    
77.                 p1 = p->rchild;
    
78.                 if (p1->bf == -1)
    
79.                 {
    
80.                         p->rchild = p1->lchild;
    
81.                         p1->lchild = p;
    
82.                         p->bf = p1->bf = 0;
    
83.                         p = p1;
    
84.                 }
    
85.                 else if (p1->bf == 1)
    
86.                 {
    
87.                         p2 = p1->lchild;
    
88.                         p1->lchild = p2->rchild;
    
89.                         p2->rchild = p1;
    
90.                         p->rchild = p2->lchild;
    
91.                         p2->lchild = p;
    
92.                         p = p2;
    
93.                         p->bf = 0;
    
94.                 }
    
95.                 taller = 0;
    
96.         }
    
97. }
    
98. 
    
99. /*在进行删除平衡二叉树的节点时候需要做相应的左平衡旋转处理*/
    
100. void LeftProcess1(AVLNode *&p, int &taller)
     
101. {
     
102.         AVLNode *p1, *p2;
     
103.         if (p->bf == 1)
     
104.         {
     
105.                 p->bf = 0;
     
106.                 taller = 1;
     
107.         }
     
108.         else if (p->bf == 0)
     
109.         {
     
110.                 p->bf = -1;
     
111.                 taller = 0;
     
112.         }
     
113.         else
     
114.         {
     
115.                 p1 = p->rchild;                                                                                                                /*RR处理*/
     
116.                 if (p1->bf == 0)
     
117.                 {
     
118.                         p->rchild = p1->lchild;
     
119.                         p1->rchild = p;
     
120.                         p1->bf = 1;
     
121.                         p->bf = -1;
     
122.                         p = p1;
     
123.                         taller = 0;
     
124.                 }
     
125.                 else if (p1->bf == -1)                                                                                                /*RR处理*/
     
126.                 {
     
127.                         p->rchild = p1->lchild;
     
128.                         p1->lchild = p;
     
129.                         p->bf = p1->bf = 0;
     
130.                         p = p1;
     
131.                         taller = 1;
     
132.                 }
     
133.                 else                                                                                                                                /*RL处理*/
     
134.                 {
     
135.                         p2 = p1->lchild;
     
136.                         p1->lchild = p2->rchild;
     
137.                         p2->rchild = p1;
     
138.                         p->rchild = p2->lchild;
     
139.                         p2->lchild = p;
     
140.                         p2->bf = 0;
     
141.                         p = p2;
     
142.                         taller = 1;
     
143.                 }
     
144.         }
     
145. }
     
146. 
     
147. /*在进行删除平衡二叉树的节点时候需要做相应的右平衡旋转处理*/
     
148. void RightProcess1(AVLNode *&p, int &taller)
     
149. {
     
150.         AVLNode *p1, *p2;
     
151.         if (p->bf == -1)
     
152.         {
     
153.                 p->bf = 0;
     
154.                 taller = -1;
     
155.         }
     
156.         else if (p->bf == 0)
     
157.         {
     
158.                 p->bf = 1;
     
159.                 taller = 0;
     
160.         }
     
161.         else                                                                                                                                        /*LL处理*/
     
162.         {
     
163.                 p1 = p->lchild;
     
164.                 if (p1->bf == 0)
     
165.                 {
     
166.                         p->lchild = p1->rchild;
     
167.                         p1->rchild = p;
     
168.                         p->bf = -1;
     
169.                         p1->bf = 1;
     
170.                         p = p1;
     
171.                         taller = 0;
     
172.                 }
     
173.                 else if (p1->bf == 1)                                                                                                /*LL处理*/
     
174.                 {
     
175.                         p->lchild = p1->rchild;
     
176.                         p1->rchild = p;
     
177.                         p->bf = p1->bf = 0;
     
178.                         p = p1;
     
179.                         taller = 1;
     
180.                 }
     
181.                 else                                                                                                                                /*LR处理*/
     
182.                 {
     
183.                         p2 = p1->rchild = p2->lchild;
     
184.                         p2->lchild = p1;
     
185.                         p->lchild = p2->rchild;
     
186.                         p2->rchild = p;
     
187.                         p2->bf = 0;
     
188.                         p = p2;
     
189.                         taller = 1;
     
190.                 }
     
191.         }
     
192. }
     
193. 
     
194. void Delete2(AVLNode *q, AVLNode *&r, int &taller)                                                        /*用于被删除节点左右子树均不为空*/
     
195. {
     
196.         if (r->rchild == NULL)
     
197.         {
     
198.                 q->key = r->key;
     
199.                 q = r;
     
200.                 r = r->lchild;
     
201.                 free(q);
     
202.                 taller = 1;
     
203.         }
     
204.         else
     
205.         {
     
206.                 Delete2(q, r->rchild, taller);
     
207.                 if (taller == 1)
     
208.                         RightProcess(r, taller);
     
209.         }
     
210. }
     
211. 
     
212. /*删除平衡二叉树的节点*/
     
213. int DeleteAVL(AVLNode *&p, KeyType x, int &taller)
     
214. {
     
215.         int k;
     
216.         AVLNode *q;
     
217.         if (p == NULL)                                                                                                                        /*如果为空树，则正常退出*/
     
218.                 return 0;
     
219.         else if (x < p->key)                                                                                                        /*如果待删除的节点小于该节点，则往它左孩子寻找*/
     
220.         {
     
221.                 k = DeleteAVL(p->lchild, x, taller);
     
222.                 if (taller == 1)                                                                                                        /**/
     
223.                         LeftProcess(p, taller);
     
224.                 return k;
     
225.         }
     
226.         else if (x > p->key)
     
227.         {
     
228.                 k = DeleteAVL(p->rchild, x, taller);
     
229.                 if (taller == 1)
     
230.                         RightProcess1(p, taller);
     
231.                 return k;
     
232.         }
     
233.         else
     
234.         {
     
235.                 q = p;
     
236.                 if (p->rchild == NULL)                                                                                                /*被删节点右子树为空*/
     
237.                 {
     
238.                         p = p->lchild;
     
239.                         free(q);
     
240.                         taller = 1;
     
241.                 }
     
242.                 else if (p->rchild == NULL)                                                                                        /*被删节点左子树为空*/
     
243.                 {
     
244.                         p = p->lchild;
     
245.                         free(q);
     
246.                         taller = 1;
     
247.                 }
     
248.                 else                                                                                                                                /*被删节点左右子树均不为空*/
     
249.                 {
     
250.                         Delete2(q, q->lchild, taller);
     
251.                         if (taller == 1)
     
252.                                 LeftProcess1(q, taller);
     
253.                         p = q;
     
254.                 }
     
255.                 return 1;
     
256.         }
     
257. }
     
258. 
     
259. /*销毁平衡二叉树*/
     
260. void DestroyAVL(AVLNode *&b)
     
261. {
     
262.         if (b->lchild)
     
263.                 DestroyAVL(b->lchild);
     
264.         if (b->rchild)
     
265.                 DestroyAVL(b->rchild);
     
266.         free(b);
     
267.         b = NULL;
     
268. }
     
269. 
     
270. /*向当前平衡二叉树插入一个元素*/
     
271. int InsertNode(AVLNode *&b, KeyType e, int &taller)
     
272. {
     
273.         if (b == NULL)                                                                                                                        /*当b为空树时进行动态分配等待插入新元素*/
     
274.         {
     
275.                 b = (AVLNode *)malloc(sizeof(AVLNode));
     
276.                 b->key = e;
     
277.                 b->lchild = b->rchild = NULL;
     
278.                 b->bf = 0;                                                                                                                        /*将平衡因子置为 0*/
     
279.                 taller = 1;                                                                                                                        /*将该节点的高度置为 1*/
     
280.         }
     
281.         else
     
282.         {
     
283.                 if (e == b->key)                                                                                                        /*如果树中已经存在该点，则无需插入*/
     
284.                 {
     
285.                         taller = 0;
     
286.                         return 0;
     
287.                 }
     
288.                 if (e < b->key)                                                                                                                /*如果待插入的数小于该节点，则往它左孩子插入*/
     
289.                 {
     
290.                         if ((InsertNode(b->lchild, e, taller)) == 0)
     
291.                                 return 0;
     
292.                         if (taller == 1)                                                                                                /*若该节点的高度为1，插入后增1，则会破坏平衡*/
     
293.                                 LeftProcess(b, taller);                                                                                /*破坏后进行左平衡旋转处理重新达到平衡*/
     
294.                 }
     
295.                 else                                                                                                                                /*否则往它右孩子插入*/
     
296.                 {
     
297.                         if ((InsertNode(b->rchild, e, taller)) == 0)
     
298.                                 return 0;
     
299.                         if (taller == 1)                                                                                                /*若该节点的高度为1，插入后增1，则会破坏平衡*/
     
300.                                 RightProcess(b, taller);                                                                        /*破坏后进行右平衡旋转处理重新达到平衡*/
     
301.                 }
     
302.         }
     
303.         return 1;
     
304. }
     
305. 
     
306. /*输出要选择操作的功能菜单*/
     
307. void OutputAVL(AVLNode *b)
     
308. {
     
309.         system("cls");
     
310.         system("color a");
     
311.         printf("\t\t******************************************\n");
     
312.         printf("\t\t*             平衡二叉树操作             *\n");
     
313.         printf("\t\t*        ==请 选 择 你 的 操 作==        *\n");
     
314.         printf("\t\t*                                        *\n");
     
315.         printf("\t\t*           A.创          建             *\n");
     
316.         printf("\t\t*           B.显          示             *\n");
     
317.         printf("\t\t*           C.查          找             *\n");
     
318.         printf("\t\t*           D.插          入             *\n");
     
319.         printf("\t\t*           E.删          除             *\n");
     
320.         printf("\t\t*           F.销          毁             *\n");
     
321.         printf("\t\t*           G.退          出             *\n");
     
322.         printf("\t\t*                                        *\n");
     
323.         printf("\t\t*     爱鱼C、爱编程、爱世界、爱和平      *\n");
     
324.         printf("\t\t*           www.bbs.fishc.com            *\n");
     
325.         printf("\t\t*                      ---By:零度非安全  *\n");
     
326.         printf("\t\t******************************************\n");
     
327. }
     
328. 
     
329. /*递归查找平衡二叉树中的元素*/
     
330. bool SearchAVLNode(AVLNode *&b, int n)
     
331. {
     
332.         if (!b)
     
333.                 return false;
     
334.         else if (n == b->key)                                                                                                /*找到了返回true*/
     
335.                 return true;
     
336.         else if (n < b->key)
     
337.                 return SearchAVLNode(b->lchild, n);                                                                /*如果小于则继续在其左孩子中查找*/
     
338.         else
     
339.                 return SearchAVLNode(b->rchild, n);                                                                /*否则就到右孩子中查找*/
     
340. }
     
341. 
     
342. /*打印平衡二叉树的状态*/
     
343. void PrintAVLNode(AVLNode *b)
     
344. {
     
345.         AVLNode *p, *St[MaxSize];
     
346.         int level[MaxSize][2], top, n, i, width = 4;
     
347.         if (b != NULL)
     
348.         {
     
349.                 top = 1;
     
350.                 St[top] = b;                                                                                                        /*将根节点入栈*/
     
351.                 level[top][0] = width;
     
352.                 while (top > 0)
     
353.                 {
     
354.                         p = St[top];
     
355.                         n = level[top][0];
     
356.                         for (i = 1; i <= n; i++)
     
357.                                 printf(" ");
     
358.                         printf("%d", p->key);
     
359.                         for (i = n + 1; i < MaxSize - 6; i += 2)
     
360.                                 printf("*");
     
361.                         printf("\n");
     
362.                         top--;
     
363.                         if (p->rchild != NULL)                                                                                /*将右孩子根节点入栈*/
     
364.                         {
     
365.                                 top++;
     
366.                                 St[top] = p->rchild;
     
367.                                 level[top][0] = n + width;
     
368.                         }
     
369.                         if (p->lchild != NULL)                                                                                /*将左孩子根节点入栈*/
     
370.                         {
     
371.                                 top++;
     
372.                                 St[top] = p->lchild;
     
373.                                 level[top][0] = n + width;
     
374.                         }
     
375.                 }
     
376.         }
     
377. }
     
378. 
     
379. /*创建一个平衡二叉树*/
     
380. AVLNode *CreateAVL(AVLNode *&b)
     
381. {
     
382.         int mainkey, i;
     
383.         b = NULL;
     
384.         printf("请输入节点(以-1结束):");
     
385.         scanf("%d", &mainkey);
     
386.         while (mainkey != -1)                                                                                                /*当输入的数不为-1时进行循环*/
     
387.         {
     
388.                 InsertNode(b, mainkey, i);
     
389.                 printf("当前二叉树状态:\n");
     
390.                 PrintAVLNode(b);
     
391.                 printf("请输入节点(以-1结束):");
     
392.                 scanf("%d", &mainkey);
     
393.         }
     
394.         return b;
     
395. }
     
396. 
     
397. /*主函数*/
     
398. int main()
     
399. {
     
400.         int node, h;
     
401.         char ch;                                                                                                                        /*定义一个输入变量*/
     
402.         while (1)                                                                                                                        /*进行循环操作*/
     
403.         {
     
404.                 OutputAVL(b);
     
405.                 printf("请选择:");
     
406.                 ch = getchar();
     
407.                 fflush(stdin);                                                                                                        /*清除输入的缓存*/
     
408.                 if (ch == 'A')                                                                                                        /*进行创建操作*/
     
409.                 {
     
410.                         system("cls");
     
411.                         printf("正在创建中......\n\n");
     
412.                         CreateAVL(b);
     
413.                         system("pause");
     
414.                 }
     
415.                 else if (ch == 'B')                                                                                                /*进行显示操作*/
     
416.                 {
     
417.                         system("cls");
     
418.                         printf("当前平衡二叉树的状态为:\n");
     
419.                         PrintAVLNode(b);
     
420.                         system("pause");
     
421.                 }
     
422.                 else if (ch == 'C')                                                                                                /*进行查找操作*/
     
423.                 {
     
424.                         system("cls");
     
425.                         printf("正在查找中......\n\n");
     
426.                         printf("请输入要查找的关键字:\n");
     
427.                         scanf("%d", &node);
     
428.                         if (SearchAVLNode(b, node))
     
429.                         {
     
430.                                 printf("查找成功!\n");
     
431.                                 PrintAVLNode(b);                                                                                /*当查找成功时输出当前平衡二叉树的状态*/
     
432.                         }
     
433.                         else
     
434.                         {
     
435.                                 printf("查找失败!\n");
     
436.                                 printf("当前平衡二叉树中根本不存在这个节点\n");                        /*当查找失败提示用户这树中不存在该节点*/
     
437.                         }
     
438.                         system("pause");
     
439.                 }
     
440.                 else if (ch == 'D')                                                                                                /*进行插入操作*/
     
441.                 {
     
442.                         system("cls");
     
443.                         printf("正在插入中......\n\n");
     
444.                         printf("请输入关键字(整数):\n");
     
445.                         scanf("%d", &node);
     
446.                         InsertNode(b, node, h);
     
447.                         system("pause");
     
448.                 }
     
449.                 else if (ch == 'E')                                                                                                /*进行删除操作*/
     
450.                 {
     
451.                         system("cls");
     
452.                         printf("正在删除中......\n\n");
     
453.                         printf("请输入关键字(整数):\n");
     
454.                         scanf("%d", &node);
     
455.                         if (DeleteAVL(b, node, h))
     
456.                         {
     
457.                                 printf("删除成功!\n");
     
458.                                 PrintAVLNode(b);                                                                                /*当删除成功时及时显示当前平衡二叉树状态*/
     
459.                         }
     
460.                         else
     
461.                                 printf("删除失败!\n");
     
462.                         system("pause");
     
463.                 }
     
464.                 else if (ch == 'F')                                                                                                /*进行销毁操作*/
     
465.                 {
     
466.                         system("cls");
     
467.                         printf("正在销毁中......\n\n");
     
468.                         DestroyAVL(b);
     
469.                         printf("销毁成功!\n");
     
470.                         system("pause");
     
471.                 }
     
472.                 else if (ch == 'G')                                                                                                /*进行退出操作*/
     
473.                         exit(0);
     
474.                 OutputAVL(b);
     
475.                 fflush(stdin);
     
476.         }
     
477.         return 0;                                                                                                                        /*程序正常退出*/
     
478. }

复制代码

源码文件： 平衡二叉树源码文件.rar (9.05 KB, 下载次数: 42)

2015-11-26 17:12 上传

点击文件名下载附件

程序文件： 平衡二叉树演示.rar (17.2 KB, 下载次数: 23)

2015-11-17 16:31 上传

点击文件名下载附件

康小泡

挺厉害啊

零度非安全

康小泡 发表于 2015-11-17 19:22
挺厉害啊

谢谢泡泡姐

浮云骑士

我还没学到，看不懂？

tinytsa86

有点看不懂。。。

小甲鱼

哈哈，看来还要想办法改进下课程~~

kmjstv

这是啥

hiwch

真厉害，不错哦。

showyoyoya

人工置顶

鱼C工作室.YCGZS

感谢分享

小小沫

厉害！！！

淫令天下

我们也开了这门课，，可似乎我们没有讲到平衡为二叉树！

郭柯宇程序猿

挺好的

dps521

过来看看  呵呵

dps521

真棒   天才啊  呵呵

zihan68

我的妈来，真厉害

zihan68

话说，代码这么长。。。

千年粽子

在吗

零度非安全

千年粽子 发表于 2015-11-30 19:28
在吗

？？？   我在的

隔壁村的严二狗

学习~