沈阳航空航天大学
课 程 设 计 报 告
课程设计名称：数据结构课程设计 课程设计题目：二叉平衡树的实现
院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师：
沈阳航空航天大学课程设计报告
目 录
1 需求分析 .................................................................................................................... 1 1.1 课程设计内容和要求 .......................................................................................... 1 1.2 算法描述 ................................................................................................................ 1 1.2.1存储结构 ........................................................................................................... 1 1.2.2 二叉排序树和二叉平衡树 ............................................................................. 1 1.2.3 层次遍历二叉树 ............................................................................................. 1 2 系统设计 .................................................................................................................... 2 2.1 总体方案设计 ........................................................................................................ 2 2.2 函数设计 ................................................................................................................ 2 2.3 关键流程 ................................................................................................................ 3 2.3.1 系统主流程 ..................................................................................................... 3 2.3.2 reat()创建链表函数流程 ................................................................................. 4 2.3.3 travel()层次遍历函数流程 .............................................................................. 5 2.3.4 B1()求左右孩子深度函数流程 ....................................................................... 6 2.3.5 B2()求节点平衡度函数流程 ........................................................................... 7 2.3.6 kind()判断节点不平衡的类型函数流程 ........................................................ 7 2.3.7 deal()转化成平衡树类型函数流程 ................................................................. 8 3 调试分析 .................................................................................................................. 10 参考文献 ........................................................................................................................ 13 附 录 .......................................................................................................................... 14
I
沈阳航空航天大学课程设计报告
1 需求分析
1.1 课程设计内容和要求
内容：
从键盘输入多组数据，生成相应的二叉排序树并将各二叉排序树转换为二叉平衡树，比较二叉排序树和二叉平衡树的平均比较长度，并将文件保存到文件中。
要求：
1．二叉排序树和二叉平衡树的存储结构自定； 2．输入数据要考虑多种情况，有代表性； 3．给出动态显示过程(选作)；
1.2 算法描述
1.2.1存储结构
二叉排序树是采用二叉链表建立，左孩子存放比父亲节点小的数，右孩子存放比父亲节点大的数。二叉排序树向二叉平衡树转化时用队列来存储每一个节点，然后层次遍历时也是用到队列，然后输出队列就为层次遍历的结果。
1.2.2 二叉排序树和二叉平衡树
用户输入数据，程序会按照层次遍历的结果建立二叉排序树，比根节点小的
数放在做孩子节点中，比根节点大的数据放入右孩子节点。二叉平衡树建立时，需要判断每个节点的平衡度，即左孩子的深度减去右孩子的深度的值的绝对值小于等于1，如果大于1，则该节点出现不平衡，从该节点开始调整成平衡。
1.2.3 层次遍历二叉树
从根节点出发,输出结点信息到队列中,然后依次遍历结点的左右孩子,每输出一结点信息,,将其存储在队列中, 遍历完结点后,队列元素出队.循环执行该过程,当队列为空时,函数执行结束。将结果再保存到文件中。
1
沈阳航空航天大学课程设计报告
2 系统设计
2.1 总体方案设计
系统的总体设计方案是：首先由用户输入数据，然后进入二叉排序函数对数
据进行排序，排完序后对每一个节点求深度，然后判断出不平衡的节点，调用平衡函数把不平衡的节点调整成平衡的节点，直到循环结束，二叉平衡树也就转换完成。然后再层次遍历二叉平衡树，输出结果并保存到文件中。
2.2 函数设计
﹙1﹚本系统所设计的函数见表2.1。
表2.1 函数列表 函数名称 main 函数原型 void main()； 功能描述 系统主程序 creat void creat(Bitree *&T); 创建一颗二叉排序树 travel queue travel(Bitree *T); 层次遍历二叉树 Deep int Deep(Bitree *T); 求树的深度 B1 void B1(Bitree *T); 完成二叉排序树的存储 B2 void B2(Bitree *T); 求每一个节点的不平衡度 kind int kind(Bitree *p, Bitree *q); 判断每个节点是什么类型的不平衡 把不平衡的二叉树转化成平衡二叉树 把输出的结果保存到文件中 deal kind deal(Bitree *&T,int data); WritetoText voidWritetoText(queue Q);
2
沈阳航空航天大学课程设计报告
﹙2﹚本系统函数的调用关系见图2.1。
开始
输入数据 调用creat函数建立二叉排序树 调用deal函数转换为平衡二叉树 调用WritetoText函数将结果保存至文件中 结束 图2.1 调用关系图
2.3 关键流程
2.3.1 系统主流程
（1）主函数的简单描述：
本函数的具体功能是：该函数是系统执行的必须函数，本函数包含其他各个子函数，经过调用，实现二叉排序树，并把二叉排序树转化成二叉平衡树。 （2）主函数的流程图 本函数的具体流程见图2.2。
开始
Bitree *T; queue qq; 二叉平衡树创建二叉排序树T转化 3
沈阳航空航天大学课程设计报告
输出二叉平衡树 层次遍历输出 将输出结果保存到文件 结束
图2.2 主函数的流程图
2.3.2 reat()创建链表函数流程
（1）创建链表函数的简单描述：
本函数的具体功能是：根据用户输入的数据创建二叉排序树。 （2）创建链表函数的流程图
本函数的具体流程见图2.3。流程图中变量i,k为控制循环的整型变量；n为要输入的数据的个数；D[100]为存储输入的数据。
开始
int i,k,D[100],n,j;
i inistall(D,n);把数据写入队列中 4 沈阳航空航天大学课程设计报告 建立二叉树 通过deal(T,D[i])函数判断二叉树的的不平衡类型 结束 图2.3 creat()函数的流程图 2.4.3 travel()层次遍历函数流程 （1）层次遍历函数的简单描述： 本函数的具体功能：层次遍历二叉树，把遍历的数据存储到链表中。 （2）层次遍历函数的流程图 本函数的具体流程见图2.4。 开始 queue q; N 队列q是否 不为空 Y Temp从队列q; 输出 N Temp->left Y Temp->left进入队列 q; N Temp->right Y N Y q; Temp->right进入队列 5 沈阳航空航天大学课程设计报告 返回q的值 ; 结束 图2.4 travel()函数的流程图 2.4.4 B1()求左右孩子深度函数流程 （1）求深度函数的简单描述： 本函数的具体功能是：完成二叉排序树的存储 （2）求深度函数的流程图 本函数的具体流程见图2.5。流程图有变量n1,n2为标记该节点的位置。 T Y N Bitree *p,*q; 开始 Bitree *p,*q; N Y N Y 调用B1函数 调用locate函数 c[n1].right=-1; 队列不为空 q=p->right; 调用locate函数 c[n1].left=-1; 队列不为空 6 沈阳航空航天大学课程设计报告 结束 图2.5 B1()函数的流程图 2.4.5 B2()求节点平衡度函数流程 （1）求节点平衡度函数的简单描述： 本函数的具体功能是：计算出每一个节点的不平衡度，为转化成二叉平衡树做铺垫。 2）求节点平衡度函数的流程图 本函数的具体流程见图2.6。 开始 int n,left,right; N T Y left= T->left的深度; right= T->right的深度; ; 结束 图2.6 B2()函数的流程图 2.4.6 kind()判断节点不平衡的类型函数流程 （1）判断节点不平衡的类型函数的简单描述： 7 沈阳航空航天大学课程设计报告 本函数的具体功能是：判断出每一个节点是RR 、RL、 LR 、LL中的哪种。 （2）判断节点不平衡的类型函数的流程图 本函数的具体流程见图2.7。流程图有变量k为标记该节点是第几种不平衡类型。 开始 Bitree *r,*s; 函数返回值 2 3 4 1 LL RR RL K=4 LR 结束 图2.7 kind()函数的流程图 返回k的值; K=2 K=3 K=1 2.4.7 deal()转化成平衡树类型函数流程 （1）转化成平衡树类型函数的简单描述： 本函数的具体功能是：从不平衡的节点开始，把节点转化平衡。 （2）转化成平衡树类型函数的流程图 本函数的具体流程见图2.8。流程图有变量k为标记该节点是第几种不平衡类型，i为循环变量，j为判断节点是否存在。 开始 int i,k=0,j,e; 8 沈阳航空航天大学课程设计报告 N C[i]的平衡因子大于2 或小于-2 Y i=c[i]双亲的位置 N C[i]的平衡因子大于1 或小于-1 Y 调用find(T,c[j].data,r); 进行平衡转换 结束 图2.8 deal()函数的流程图 9 沈阳航空航天大学课程设计报告 3 调试分析 (1) 问题1 问题描述：输入数据后，输出的二叉树层次遍历不准确。 问题分析：deal函数编译错误，搞错了LL与LR类型。 解决方法：进入单部调试函数，跟踪每个参数，一点一点找到问题所在 并改正。 (2) 问题2 问题描述： 无法将数据保存到文件中。 问题分析：可能是文件读写错误或者队列应用错误 解决方法：检查文件的读写，设置一个新的参数将树中的值传给它，用 它完成文件的保存。 10 沈阳航空航天大学课程设计报告 4 测试及运行结果 （1） 进入操作界面如图4.1所示。 图4.1 操作界面结果 （2）输入多组数据的具体的测试结果如图4.2所示。 图4.2 多组数据测试结果 （3）经层次遍历后的平衡二叉树输出数据的具体的测试结果如图4.3所示。 11 沈阳航空航天大学课程设计报告 图4.3 输出数据测试结果 （2） 测试结果保存到到D盘的二叉平衡树的文件中如图4.4所示。 图4.4保存到文件中 12 沈阳航空航天大学课程设计报告 参考文献 [1] 严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，2007 [2] 谭浩强.C程序设计（第三版）.清华大学出版社，2009 [3] 高一凡. 数据结构算法分析.清华大学出版社，2008 [4] 张长海.C程序设计.高等教育出版社，20004 [5] 王裕明.数据结构与程序设计.清华大学出版社，2010 [6] 王曙燕 曹锰. C语言程序设计. 科学出版社，2005 13 沈阳航空航天大学课程设计报告 附 录 源程序清单： #include typedef struct Bitree { int data; struct Bitree *right; struct Bitree *left; }Bitree; typedef struct { Bitree *base; int top; int bottom; int size; }queue; BF c[100]; void inistall(queue &q) { q.base=(Bitree *)malloc(sizeof(Bitree)*100); q.top=q.bottom=0; q.size=100; } void push(Bitree t,queue &q) { if(q.top==100) printf(\"queue full\\n\"); q.base[q.top++]=t; } int empty(queue q) { 14 沈阳航空航天大学课程设计报告 if(q.top==q.bottom) return 1; else return 0; } void pop(Bitree *&temp,queue &q) { if(q.top==q.bottom) printf(\"queue null\\n\"); else temp=&(q.base[q.bottom++]); } queue travel(Bitree *t) { queue q; Bitree *temp; inistall(q); push(*t,q); while(!empty(q)) { pop(temp,q); printf(\"%d \ 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; else { right=Deep(T->right); left=Deep(T->left); if(right>left) k=1+right; else k=1+left; } return k; 15 沈阳航空航天大学课程设计报告 } int locate(int n) { int i; for(i=0;i<100;i++) if(c[i].data==n) return i; } void B1(Bitree *T) { Bitree *p,*q; int n1,n2; if(T) { p=T; q=p->left; n1=locate(p->data); if(q!=NULL) {n2=locate(q->data); c[n1].left=n2; c[n2].parent=n1; } else { c[n1].left=-1; } q=p->right; n1=locate(p->data); if(q!=NULL) {n2=locate(q->data); c[n1].right=n2; c[n2].parent=n1; } else { c[n1].right=-1; } B1(T->left); B1(T->right); } } void B2(Bitree *T) { 16 沈阳航空航天大学课程设计报告 int n,left,right; if(T) { left=Deep(T->left); right=Deep(T->right); n=locate(T->data); c[n].bf=left-right; B2(T->left); B2(T->right); } } void B(Bitree *T) { int i; for(i=0;i<100;i++) c[i].parent=c[i].left=c[i].right=-1; B1(T); B2(T); } void inistall(int a[],int n) { int i; for(i=0;i int hunt(Bitree *p,Bitree *q) { 17 沈阳航空航天大学课程设计报告 if(p) { if(p->data==q->data) return 1; else { if(hunt(p->left,q)) return 1; else return 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;//RR s=r->left; if((s!=NULL)&&(hunt(s,q))) k=3;//RL } if(p->left!=NULL) { r=p->left; s=r->right; if((s!=NULL)&&(hunt(s,q))) k=4;//LR s=r->left; if((s!=NULL)&&(hunt(s,q))) k=1;//LL } return k; } int pos(Bitree *r,Bitree *q) { int k; 18 沈阳航空航天大学课程设计报告 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(c[i].bf<2&&c[i].bf>-2&&i!=-1) i=c[i].parent; if((c[i].bf>1||c[i].bf<-1)&&(i!=-1)) { find(T,c[i].data,p); j=c[i].parent; find(T,data,q); if(j!=-1)//r存在 { find(T,c[j].data,r); e=pos(r,p);//e:1为p是r的右孩子 2为p是r的左孩子 k=kind(p,q);//1:LL 2:RR 3:RL 4:LR if(e==1)//p是r的右孩子 { switch(k) { case 1:r->right=p->left; p->left=r->right->right; r->right->right=p; break; case 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; 19 沈阳航空航天大学课程设计报告 p->left=temp; p->left=temp->right; temp->right=p; r->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=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->left=temp; break; default:break; } } B(T); } else//A为头结点 { 20 沈阳航空航天大学课程设计报告 k=kind(p,q);//1:LL 2:RR 3:RL 4:LR switch(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; 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,D[1000],n,j; Bitree *p,*q,*R,*S,*G; printf(\"\请输入数据个数:\"); scanf(\"%d\ getchar(); for(i=0;i 沈阳航空航天大学课程设计报告 scanf(\"%d\ } inistall(D,n); for(i=0;i void WritetoText(Bitree *t) /*将所有记录写入文件*/ { FILE *fp; /*定义文件指针*/ Bitree *temp; queue q; int s; inistall(q); push(*t,q); fp=fopen(\"d:\\\\二叉平衡树.txt\打开文件*/ 22 沈阳航空航天大学课程设计报告 while(!empty(q)) { pop(temp,q); printf(\"%d \ s=temp->data; fprintf(fp,\"%d\\n\ if(temp->left) push(*temp->left,q); if(temp->right) push(*temp->right,q); } fclose(fp); /*关闭文件*/ printf(\"\\n\\\Successed!\\n\"); /*返回成功信息*/ } void show() { printf(\"\**************************************************\\n\"); printf(\"\\n\"); printf(\"\\\请二叉平衡树的实现\\n\"); printf(\"\\n\"); printf(\"\**************************************************\\n\"); printf(\"\注：请输入任意不重复的数字，本程序会先转换为二叉排序树\\n\"); printf(\"\ 再转化为二叉平衡树经层次遍历输出并保存到D盘的文件中\\n\"); } void main() { Bitree *T; queue qq; show(); loop:creat(T); printf(\"\生成的平衡二叉树为:\"); travel(T); WritetoText(T); goto loop; } 23 沈阳航空航天大学课程设计报告 课程设计总结： 本次课程设计，使我认识到自己的不足，不仅是对知识掌握的不足还有对编程环境应用的不足。我会在以后的学习中好好学习、正确学习，真正的使自己学到知识。 通过课程设计，我巩固了以前学过的C语言的知识，在这次课程设计中我体 会到数据结构具有超强的逻辑性，练习了VC++的编译环境的使用，也对数据结构和C语言这门两门课程有了新的认识，他们既有联系，又有区别。在编写程序过程中要灵活应用。不同的人会选择不同的算法，所以即使同样的程序，不同的人必然会设计出不同的方案，所以以后的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的算法。 总之，课程设计是对我们的一种挑战，以后我要继续认真学习有关计算机这门学科知识，多阅读些算法书籍，多上机进行编程练习，挑战无极限，我期待新的挑战到来。 指导教师评语： 指导教师(签字)： 年 月 日 课程设计成绩 24
因篇幅问题不能全部显示，请点此查看更多更全内容