二叉平衡树的实现---数据结构课程设计.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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 平衡 实现 数据结构 课程设计
限制150内