二叉平衡排序树

1、数据结构课程设计数据结构课程设计报告 设计题目： 二叉平衡排序树 姓名： 黄洪飞 学号： 211111014 专业： 嵌入式软件 院系：计算机科学与技术学院 班级： 1103班 指导教师： 高秀梅2013年 1 月 30 日 摘要 数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力，培养科学的软件工作方法。 数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且也已经成为其他理工专业的热门选修课。随着高级语言的发展，数据结构在计算机

2、的研究和应用中已展现出强大的生命力，它兼顾了诸多高级语言的特点，是一种典型的结构化程序设计语言，它处理能力强，使用灵活方便，应用面广，具有良好的可移植性。英文摘要Data structure is a strong theoretical thinking, abstract and difficult course, is a bridge between fundamental course and specialized course. The course of the first course is basic computer, program design language, d

3、iscrete mathematics, etc, the subsequent course has operating system, compiling principle, principle of database, software engineering, etc. Through this course of study, we should be able to a thorough understanding of the characteristics of various data objects, and learn to data organization meth

4、od and implementation methods, and further cultivate good program design ability and the ability to solve practical problems. Data structure is a computer science and technology professional a core the basis of professional course, in the professional course system plays an essential role, learn dat

5、a structure to improve the cognitive level of theory and practice ability has a very important role. Learning data structure of the ultimate goal is to gain the ability of solving problem. For the real world problems, should be able to abstract out an appropriate mathematical model, the mathematical

6、 model in computer internal with the corresponding data structure to say, and then design a solution of the mathematical model of the algorithm, and then to programming debugging, and finally get the answer. In order to strengthen the practice course is programming ability training, and encourage st

7、udents to use the new programming language. We believe that through the data structure course practice, both theoretical knowledge and practical ability, or we will have different degree of increase 目 录一、 问题5二、需求分析5三、概要设计5四、数据结构设计6五、算法设计6六、程序测试与实现8七、调试分析11八、遇到的问题及解决办法11九、心得体会111、 问题问题描述：创建二叉平衡排序树基本要

8、求：1.输入数据的数量不得低于15个2.建立二叉平衡排序树（要求包括LL型LR型RR型RL型四种调整方式）3.完成任意数据的查找（要求给出查找执行的次数）二、需求分析1.本程序的功能包括二叉平衡排序树的建立，二叉平衡排序树的查询，二叉平衡排序树的输出。2.程序运行后显现提示信息，等候用户输入1-3以进入相应的操作功能，以及控制程序循环的功能。3.用户输入数据完毕，程序将输出运行结束。4.测试数据应为二叉平衡排序树每个结点的数据。三、概要设计带头结点的单链表抽象数据类型定义为：ADT AVLtree属性： AVLnode * root;操作集合： void insert(const T & x,

9、AVLnode * &t);/树的建立void makeEmpty(AVLnode * &t)/树的销毁int height(AVLnode *t)constreturn t=NULL? -1:t-height;/树的高度void LL(AVLnode * &t); /树void LR(AVLnode * &t);/ 的void RL(AVLnode * &t); / 调void RR(AVLnode * &t);/ 整int max(int a,int b)return (ab)?a:b; /结点数值比大小void printin(AVLnode * t,int depth);/树的打印AD

10、T AVLtree；四、数据结构设计元素类型，结点类型，指针类型 typedef struct AVLnode /结点类型定义 T data; /结点数据域 struct AVLnode *left; /结点左指针域 struct AVLnode *right; /结点右指针域 Int height/树的高度AVLnode;五、算法设计 1、算法分析与实现 template void AVLtree:insert(const T & x,AVLnode * &t) if(t=NULL)/空树上插入 t=new AVLnode(x,NULL,NULL); else if(xdata)/在左子树上

11、插入 insert(x,t-left);/从左边插入 if(height(t-left)-height(t-right)=2)/t失去平衡 if(xleft-data)LL(t);else LR(t);/进行调整 else if(t-dataright);/在右子树上插入 if(height(t-right)-height(t-left)=2)/t失去平衡 if(t-right-dataheight=max(height(t-left),height(t-right)+1;/重新计算t的高度template void AVLtree:LL(AVLnode * &t)AVLnode *t1=t-

12、left;/定临时变量t-left=t1-right;t1-right=t;t-height=max(height(t-left),height(t-right)+1;t1-height=max(height(t1-left),height(t)+1;t=t1;template void AVLtree:LR(AVLnode * &t)RR(t-left);LL(t);template bool AVLtree:find(const T &x)constint count=1;/计数变量AVLnode *t=root;/定义临时变量while(t!=NULL & t-data!=x)count

13、+;计数边量+1if(t-datax)t=t-left;elset=t-right; cout比较次数:count;/输出查找的次数 cout查找结果:;if(t=NULL)return false;elsereturn true;template void AVLtree:printin(AVLnode * t,int depth=1)if(t!=NULL)printin(t-right,depth+1);/递归调用for(int i=0;i4*(depth-1);i+)coutright=NULL & t-left=NULL)coutdataendl;else coutdata left,

14、depth+1); 六、程序测试与实现1、函数之间的调用关系mainmenu insert()find()printin() Hieght() RR() LL() LR() RL() RR() LL() RR() LL() Max() 2、主程序 int main() AVLtree obj;while(true) meus(); coutn; switch(n) case 1: coutm; obj.insert(m); break; case 2: couti; coutobj.find(i); coutendl; break; case 3: cout打印结果为:endl;obj.pri

15、ntin(); break; default: cout您输入的不正确!endl; coutch; if(ch=N | ch=n) return 0; return 0; 3、 测试数据 65,89,46,25,52,87,97,75 4、 测试结果 7、 调试分析1链表中的结点变量是通过指针变量来访问的。因为在C语言中是用P来表示P所指的变量，又由于结点类型是一个结构类型，因此可用P data，Pleft，p-right 分别表示结点的数据域变量和指针域变量。指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。注意，当P为空值时，则它不指向任何结点

16、，此时不能通过P来访问结点，否则会引起程序错误。2算法的时空分析： 二叉排序树的查找 在二叉排序树中进行查找的过程和二分查找类似也是一个通过比较关键字逐步缩小查找范围的过程。 若查找成功则是一条从根结点到待查结点的路径若查找失败则是一条根结点到某个叶子结点的路径由上可知查找过程中和关键字比较的次数不超过树的深度。 二 二叉排序树查找的性能分析 由于所要查找的数据量不同则其查找的性能也不同。且二叉排序树的平均查找长度与树的形态有关。最好情况是二叉排序树和二叉判定树形态相同最坏情况是二叉排序树为单支树则其平均查找长度与顺序查找相同。 分别输入不同的二叉排序树观察并计算其平均查找长度及时间空间复杂度

17、 将已给的信息建立二叉树且根据学号查找数据并显示并判断此方法的性能。 八、遇到的问题及解决办法1.怎样才能使得存储在内存中的数据结构更加直观的表现出来？ 解决方法：将二叉树倒过来打印。2. 函数的递归调用不是很明白？ 解决方法：使用栈画图来理解。9、 心得体会回顾起此次课程设计，感慨颇多，从理论到实践，在整整两个星期的日子里，我学到很多很多的东西，不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的内容。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才是真正的知识，才能提高自己的实际动手能力和

18、独立思考的能力。在设计的过程遇到了各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计，把以前所学过的知识重新温故，巩固了所学的知识。 课程设计是一门综合性的实践性课程，课程设计能够培养我们发现问题分析问题和解决问题的能力，对于我们编写程序，合理运用各种语法也有一定的提高。同时课程设计还有利于我们及时了解和掌握所学的相关知识。我一千次一万次的问自己，怎么才能找到课堂所学与实际应用的最佳结合点？怎么才能让自己的程序在篇幅上简单，在使用价值上丰富？怎样让自己的业余更靠近专业？怎样让自己的计划更具有序性，而不会忙无一用？机会是老师

19、，学校，以及无数代教育工作者给的，而能力是自己的，耐性是需要的。经过自己的琢磨，听取了师姐，师兄们的建议，还查阅了很多书籍，才做到了心中有数，才了解了算法设计与分析课程设计的真正用意培养自学能力，养成程序编辑的好习惯。我从来不相信车到山前必有路的说法，认为那只是懒惰者自寻懒惰的借口，我要积极，要把握，要努力。不知不觉，时间就迅速地渡过了，我开始慌张起来，因为我还有许多程序代码不太明白，我又急急的去图书馆查了更多相关资料，我才发现原来我所学的知识真的很有限，我试着去调试，结果失败了好多次，我也不知道问题出现在哪里，我问了几位同学，他们热情地给我提供帮助，在他们的启迪下，我经过修改，终于通过的调试

20、。当我把调好的程序拿去给老师看是否合理时，老师给我提出了用键盘输入数据的灵活运用方法。在老师的指导下，更新后的程序就初见眉目。这更加强了我的信心，我时常去上机调试程序，运行程序，修改程序。不懂时及时请教指导老师，老师便会认真负责耐心的讲解起来。我想要是没有老师的帮助，我的此次课设就不会顺利完成。在此，我很诚挚地谢谢指导过我的老师们， 在我程序混乱时，老师没有批评我，而是很耐心的给我讲解哪些是重复的，哪些是错误的，哪些是必要的，老师就是世界上最最伟大的人。谢谢你！我的老师们。从拿到题目到完成整个编程，从理论到实践，可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本

21、上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，一定把以前所学过的知识重新温故。没有辛苦的历程就无法感受甜美的收获。在此次课程设计中，我不但运用了算法设计与分析的思想，还利用了C+语言方面的知识。这对于我来说是一个突破。从中我也学习到