1、 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：二叉平衡树的实现二叉平衡树的实现 院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师： I 目目 录录 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、 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 1 1 需求分析 1.1 课程设计内容和要求课程设计内容和要求 内容： 从键盘输入多组数据，生成相应的二叉排序树并将各二叉排序树转换为二叉 平衡树， 比较二叉排序树和二叉平衡树的平均比较长度， 并将文件保存到文件中。 要求： 1二叉排序树和二叉平衡树的存储
3、结构自定； 2输入数据要考虑多种情况，有代表性； 3给出动态显示过程(选作)； 1.2 算法描述算法描述 1.2.1 存储结构存储结构 二叉排序树是采用二叉链表建立，左孩子存放比父亲节点小的数，右孩子存 放比父亲节点大的数。 二叉排序树向二叉平衡树转化时用队列来存储每一个节点， 然后层次遍历时也是用到队列，然后输出队列就为层次遍历的结果。 1.2.2 二叉排序树和二叉平衡树二叉排序树和二叉平衡树 用户输入数据，程序会按照层次遍历的结果建立二叉排序树，比根节点小的 数放在做孩子节点中，比根节点大的数据放入右孩子节点。二叉平衡树建立时， 需要判断每个节点的平衡度，即左孩子的深度减去右孩子的深度的值
4、的绝对值小 于等于 1，如果大于 1，则该节点出现不平衡，从该节点开始调整成平衡。 1.2.3 层次遍历二叉树层次遍历二叉树 从根节点出发,输出结点信息到队列中,然后依次遍历结点的左右孩子,每输 出一结点信息,将其存储在队列中, 遍历完结点后,队列元素出队.循环执行该过 程,当队列为空时,函数执行结束。将结果再保存到文件中。 2 2 系统设计 2.1 总体方案设计总体方案设计 系统的总体设计方案是：首先由用户输入数据，然后进入二叉排序函数对数 据进行排序，排完序后对每一个节点求深度，然后判断出不平衡的节点，调用平 衡函数把不平衡的节点调整成平衡的节点，直到循环结束，二叉平衡树也就转换 完成。然
5、后再层次遍历二叉平衡树，输出结果并保存到文件中。 2.2 函数设计函数设计 1本系统所设计的函数见表 2.1。 表 2.1 函数列表 函数名称 函数原型 功能描述 main void main()； 系统主程序 creat void creat(Bitree * 创建一颗二叉排序树 travel queue travel(Bitree *T); 层次遍历二叉树 Deep int Deep(Bitree *T); 求树的深度 B1 void B1(Bitree *T); 完成二叉排序树的存储 B2 void B2(Bitree *T); 求每一个节点的不平衡度 kind int kind(Bit
6、ree *p, Bitree *q); 判断每个节点是什么类型的不平衡 deal kind deal(Bitree * 把不平衡的二叉树转化成平衡二叉 树 WritetoText voidWritetoText(queue Q); 把输出的结果保存到文件中 3 2本系统函数的调用关系见图 2.1。 图 2.1 调用关系图 2.3 关键流程关键流程 2.3.1 系统主流程系统主流程 （1）主函数的简单描述： 本函数的具体功能是： 该函数是系统执行的必须函数， 本函数包含其他各个 子函数，经过调用，实现二叉排序树，并把二叉排序树转化成二叉平衡树。 （2）主函数的流程图 本函数的具体流程见图 2.2。 调用 creat 函数建立二叉排序树 调用 deal 函数转换为平衡二叉树 调用 WritetoText 函数将结果保存至文件中 Bitree *T; queue qq; 二叉平衡树创建二叉排序树 T 转化 开始 结束 输入数据 开始 4 图 2.2 主函数的流程图 2.3.2 reat()创建链表函数流程创建链表函数流程 （1）创建链表函数的
