二叉平衡树的实现---数据结构课程设计.doc

《二叉平衡树的实现---数据结构课程设计.doc》由会员分享，可在线阅读，更多相关《二叉平衡树的实现---数据结构课程设计.doc（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date二叉平衡树的实现-数据结构课程设计数据结构课程设计模板沈阳航空航天大学课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：二叉平衡树的实现院（系）：计算机学院专 业：计算机科学与技术班 级： 学 号：姓 名： 指导教师： -目 录1 需求分析11.1 课程设计内容和要求11.2 算法描述11.2.1存储结构11.2.2 二叉排序树和二叉平衡树11.2.3

2、 层次遍历二叉树12 系统设计22.1 总体方案设计22.2 函数设计22.3 关键流程42.3.1 系统主流程42.3.2 reat()创建链表函数流程52.3.3 travel()层次遍历函数流程62.3.4 B1()求左右孩子深度函数流程72.3.5 B2()求节点平衡度函数流程82.3.6 kind()判断节点不平衡的类型函数流程92.3.7 deal()转化成平衡树类型函数流程103 调试分析11参考文献14附 录15 1 需求分析1.1 课程设计内容和要求内容：从键盘输入多组数据，生成相应的二叉排序树并将各二叉排序树转换为二叉平衡树，比较二叉排序树和二叉平衡树的平均比较长度，并将文

3、件保存到文件中。要求：1二叉排序树和二叉平衡树的存储结构自定；2输入数据要考虑多种情况，有代表性；3给出动态显示过程(选作)；1.2 算法描述1.2.1存储结构二叉排序树是采用二叉链表建立，左孩子存放比父亲节点小的数，右孩子存放比父亲节点大的数。二叉排序树向二叉平衡树转化时用队列来存储每一个节点，然后层次遍历时也是用到队列，然后输出队列就为层次遍历的结果。1.2.2 二叉排序树和二叉平衡树 用户输入数据，程序会按照层次遍历的结果建立二叉排序树，比根节点小的数放在做孩子节点中，比根节点大的数据放入右孩子节点。二叉平衡树建立时，需要判断每个节点的平衡度，即左孩子的深度减去右孩子的深度的值的绝对值小

4、于等于1，如果大于1，则该节点出现不平衡，从该节点开始调整成平衡。1.2.3 层次遍历二叉树 从根节点出发,输出结点信息到队列中,然后依次遍历结点的左右孩子,每输出一结点信息,将其存储在队列中, 遍历完结点后,队列元素出队.循环执行该过程,当队列为空时,函数执行结束。将结果再保存到文件中。2 系统设计2.1 总体方案设计 系统的总体设计方案是：首先由用户输入数据，然后进入二叉排序函数对数据进行排序，排完序后对每一个节点求深度，然后判断出不平衡的节点，调用平衡函数把不平衡的节点调整成平衡的节点，直到循环结束，二叉平衡树也就转换完成。然后再层次遍历二叉平衡树，输出结果并保存到文件中。2.2 函数设

5、计1本系统所设计的函数见表2.1。表2.1 函数列表函数名称函数原型功能描述mainvoid main()；系统主程序creatvoid creat(Bitree *&T);创建一颗二叉排序树travelqueue travel(Bitree *T);层次遍历二叉树Deepint Deep(Bitree *T);求树的深度B1void B1(Bitree *T); 完成二叉排序树的存储B2void B2(Bitree *T);求每一个节点的不平衡度kindint kind(Bitree *p, Bitree *q);判断每个节点是什么类型的不平衡dealkind deal(Bitree *&T

6、,int data);把不平衡的二叉树转化成平衡二叉树WritetoTextvoidWritetoText(queue Q);把输出的结果保存到文件中 2本系统函数的调用关系见图2.1。开始输入数据调用creat函数建立二叉排序树调用deal函数转换为平衡二叉树调用WritetoText函数将结果保存至文件中结束图2.1 调用关系图2.3 关键流程2.3.1 系统主流程（1）主函数的简单描述：本函数的具体功能是：该函数是系统执行的必须函数，本函数包含其他各个子函数，经过调用，实现二叉排序树，并把二叉排序树转化成二叉平衡树。（2）主函数的流程图 本函数的具体流程见图2.2。开始Bitree *T

7、; queue qq;二叉平衡树创建二叉排序树T转化输出二叉平衡树层次遍历输出将输出结果保存到文件结束图2.2 主函数的流程图2.3.2 reat()创建链表函数流程（1）创建链表函数的简单描述：本函数的具体功能是：根据用户输入的数据创建二叉排序树。（2）创建链表函数的流程图 本函数的具体流程见图2.3。流程图中变量i,k为控制循环的整型变量；n为要输入的数据的个数；D100为存储输入的数据。开始printf(第%d个数据：n,i+1);int i,k,D100,n,j; ileft进入队列q;Temp从队列q;输出 YTemp-left N YTemp-right NY NYTemp-rig

8、ht进入队列q; 返回q的值;结束图2.4 travel()函数的流程图2.4.4 B1()求左右孩子深度函数流程（1）求深度函数的简单描述：本函数的具体功能是：完成二叉排序树的存储（2）求深度函数的流程图开始本函数的具体流程见图2.5。流程图有变量n1,n2为标记该节点的位置。队列不为空调用locate函数 Bitree *p,*q; T Bitree *p,*q; Y N 队列不为空 N cn1.left=-1; Yq=p-right; N调用locate函数cn1.right=-1; Y 调用B1函数结束图2.5 B1()函数的流程图2.4.5 B2()求节点平衡度函数流程（1）求节点平

9、衡度函数的简单描述：本函数的具体功能是：计算出每一个节点的不平衡度，为转化成二叉平衡树做铺垫。2）求节点平衡度函数的流程图本函数的具体流程见图2.6。开始int n,left,right; T NYleft= T-left的深度; right= T-right的深度;结束图2.6 B2()函数的流程图2.4.6 kind()判断节点不平衡的类型函数流程（1） 判断节点不平衡的类型函数的简单描述： 本函数的具体功能是：判断出每一个节点是RR 、RL、 LR 、LL中的哪种。（2）判断节点不平衡的类型函数的流程图本函数的具体流程见图2.7。流程图有变量k为标记该节点是第几种不平衡类型。开始Bitr

10、ee *r,*s;函数返回值 2 3 4 1 LR RL LL RR K=2 K=4 K=3 K=1返回k的值;结束图2.7 kind()函数的流程图2.4.7 deal()转化成平衡树类型函数流程（1）转化成平衡树类型函数的简单描述：本函数的具体功能是：从不平衡的节点开始，把节点转化平衡。（2）转化成平衡树类型函数的流程图 本函数的具体流程见图2.8。流程图有变量k为标记该节点是第几种不平衡类型，i为循环变量，j为判断节点是否存在。开始 int i,k=0,j,e;Ci的平衡因子大于2或小于-2 N i=ci双亲的位置 YCi的平衡因子大于1或小于-1 N Y 调用find(T,cj.dat

11、a,r); 进行平衡转换结束图2.8 deal()函数的流程图3 调试分析 (1) 问题1l 问题描述：输入数据后，输出的二叉树层次遍历不准确。l 问题分析：deal函数编译错误，搞错了LL与LR类型。l 解决方法：进入单部调试函数，跟踪每个参数，一点一点找到问题所在 并改正。(2) 问题2l 问题描述： 无法将数据保存到文件中。l 问题分析：可能是文件读写错误或者队列应用错误l 解决方法：检查文件的读写，设置一个新的参数将树中的值传给它，用它完成文件的保存。4 测试及运行结果（1） 进入操作界面如图4.1所示。图4.1 操作界面结果（2）输入多组数据的具体的测试结果如图4.2所示。 图4.2

12、 多组数据测试结果（3）经层次遍历后的平衡二叉树输出数据的具体的测试结果如图4.3所示。 图4.3 输出数据测试结果（2） 测试结果保存到到D盘的二叉平衡树的文件中如图4.4所示。图4.4保存到文件中参考文献1 严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，2007 2 谭浩强.C程序设计（第三版）.清华大学出版社，20093 高一凡. 数据结构算法分析.清华大学出版社，20084 张长海.C程序设计.高等教育出版社，20004 5 王裕明.数据结构与程序设计.清华大学出版社，20106 王曙燕 曹锰. C语言程序设计. 科学出版社，2005 附 录源程序清单：#include#

13、includetypedef struct BFint data;int parent;int left;int right;int bf;BF;typedef struct Bitreeint data;struct Bitree *right;struct Bitree *left;Bitree;typedef structBitree *base;int top;int bottom;int size;queue;BF c100;void inistall(queue &q)q.base=(Bitree *)malloc(sizeof(Bitree)*100);q.top=q.botto

14、m=0;q.size=100;void push(Bitree t,queue &q)if(q.top=100)printf(queue fulln);q.baseq.top+=t; int empty(queue q)if(q.top=q.bottom)return 1;else return 0;void pop(Bitree *&temp,queue &q)if(q.top=q.bottom)printf(queue nulln);else temp=&(q.baseq.bottom+);queue travel(Bitree *t)queue q;Bitree *temp;inista

15、ll(q);push(*t,q); while(!empty(q)pop(temp,q);printf(%d ,temp-data);if(temp-left)push(*temp-left,q);if(temp-right)push(*temp-right,q);return q;int Deep(Bitree *T)int k,left,right;if(!T)k=0;elseright=Deep(T-right);left=Deep(T-left);if(rightleft)k=1+right;else k=1+left;return k;int locate(int n)int i;f

16、or(i=0;ileft;n1=locate(p-data);if(q!=NULL)n2=locate(q-data);cn1.left=n2;cn2.parent=n1;elsecn1.left=-1;q=p-right;n1=locate(p-data);if(q!=NULL)n2=locate(q-data);cn1.right=n2;cn2.parent=n1;elsecn1.right=-1; B1(T-left);B1(T-right);void B2(Bitree *T)int n,left,right;if(T)left=Deep(T-left);right=Deep(T-ri

17、ght);n=locate(T-data);cn.bf=left-right;B2(T-left);B2(T-right);void B(Bitree *T)int i;for(i=0;i100;i+)ci.parent=ci.left=ci.right=-1;B1(T);B2(T);void inistall(int a,int n)int i;for(i=0;idata=data)p=T;find(T-left,data,p);find(T-right,data,p);int hunt(Bitree *p,Bitree *q)if(p)if(p-data=q-data)return 1;e

18、lse if(hunt(p-left,q)return 1;elsereturn hunt(p-right,q);else return 0;int kind(Bitree *p,Bitree *q)Bitree *r,*s;int k;if(p-right!=NULL)r=p-right;s=r-right;if(s!=NULL)&(hunt(s,q)k=2;/RRs=r-left;if(s!=NULL)&(hunt(s,q)k=3;/RLif(p-left!=NULL)r=p-left;s=r-right;if(s!=NULL)&(hunt(s,q)k=4;/LRs=r-left;if(s

19、!=NULL)&(hunt(s,q)k=1;/LLreturn k;int pos(Bitree *r,Bitree *q)int k;if(r-left=q)k=2; if(r-right=q)k=1;return k;void deal(Bitree *&T,int data)int i,k=0,j,e;Bitree *p,*q,*r,*temp;i=locate(data);while(ci.bf-2&i!=-1)i=ci.parent;if(ci.bf1|ci.bfright=p-left;p-left=r-right-right;r-right-right=p;break;case

20、2:r-right=p-right;p-right=r-right-left;r-right-left=p;break;case 3:temp=p-right-left;p-right-left=temp-right;temp-right=p-right;p-right=temp;p-right=temp-left;temp-left=p;r-right=temp;break;case 4:temp=p-left-right;p-left-right=temp-left;temp-left=p-left;p-left=temp;p-left=temp-right;temp-right=p;r-

21、right=temp;break;default:break;if(e=2)/p是r的左孩子 switch(k)case 1:r-left=p-left;p-left=r-left-right;r-left-right=p;break;case 2:r-left=p-right;p-right=r-left-left;r-left-left=p;break;case 3:temp=p-right-left;p-right-left=temp-right;temp-right=p-right;p-right=temp;p-right=temp-left;temp-left=p;r-left=te

22、mp;break;case 4:temp=p-left-right;p-left-right=temp-left;temp-left=p-left;p-left=temp;p-left=temp-right;temp-right=p;r-left=temp;break;default:break;B(T);else/A为头结点 k=kind(p,q);/1:LL 2:RR 3:RL 4:LRswitch(k)case 1:T=p-left;p-left=T-right;T-right=p;break;case 2:T=p-right;p-right=T-left;T-left=p;break;

23、case 3:temp=p-right-left;p-right-left=temp-right;temp-right=p-right;p-right=temp;p-right=temp-left;temp-left=p;T=temp;break;case 4:temp=p-left-right;p-left-right=temp-left;temp-left=p-left;p-left=temp;p-left=temp-right;temp-right=p;T=temp;break;default:break;B(T); void creat(Bitree *&T)int i,k,D1000

24、,n,j;Bitree *p,*q,*R,*S,*G;printf(t请输入数据个数:);scanf(%d,&n);getchar();for(i=0;in;i+)printf(t第%d个数据:,i+1);scanf(%d,&Di);inistall(D,n);for(i=0;idata=Di;p-left=p-right=NULL;B(T);continue;q=(Bitree *)malloc(sizeof(Bitree);q-data=Di;q-left=q-right=NULL;p=T;while(p!=NULL)G=p;if(Dip-data)p=p-right;elsep=p-le

25、ft;if(DiG-data)G-right=q;elseG-left=q;B(T);deal(T,Di);/for void WritetoText(Bitree *t) /*将所有记录写入文件*/ FILE *fp; /*定义文件指针*/ Bitree *temp;queue q; int s; inistall(q);push(*t,q); fp=fopen(d:二叉平衡树.txt,w); /*打开文件*/ while(!empty(q)pop(temp,q);printf(%d ,temp-data);s=temp-data;fprintf(fp,%dn,s);if(temp-left

26、)push(*temp-left,q);if(temp-right)push(*temp-right,q); fclose(fp); /*关闭文件*/ printf(ntttSuccessed!n); /*返回成功信息*/ void show() printf(t*n); printf(n); printf(ttt请二叉平衡树的实现n); printf(n); printf(t*n); printf(t注：请输入任意不重复的数字，本程序会先转换为二叉排序树n); printf(t 再转化为二叉平衡树经层次遍历输出并保存到D盘的文件中n); void main()Bitree *T;queue

27、qq;show();loop:creat(T);printf(t生成的平衡二叉树为:); travel(T);WritetoText(T);goto loop;课程设计总结：本次课程设计，使我认识到自己的不足，不仅是对知识掌握的不足还有对编程环境应用的不足。我会在以后的学习中好好学习、正确学习，真正的使自己学到知识。通过课程设计，我巩固了以前学过的C语言的知识，在这次课程设计中我体会到数据结构具有超强的逻辑性，练习了VC+的编译环境的使用，也对数据结构和C语言这门两门课程有了新的认识，他们既有联系，又有区别。在编写程序过程中要灵活应用。不同的人会选择不同的算法，所以即使同样的程序，不同的人必然会设计出不同的方案，所以以后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的算法。总之，课程设计是对我们的一种挑战，以后我要继续认真学习有关计算机这门学科知识，多阅读些算法书籍，多上机进行编程练习，挑战无极限，我期待新的挑战到来。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩