数据结构课程设计-带父亲节点的平衡二叉树的建立

《数据结构课程设计-带父亲节点的平衡二叉树的建立》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、XXX航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：带父亲节点的平衡二叉树的建立院（系）：计算机学院专业：网络工程班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告目录1课程设计介绍11.1课程设计内容11.2课程设计要求12课程设计原理22.1课设题目粗略分析22.2原理图介绍22.2.1功能模块图22.2.2流程图分析33数据结构分析83.1存储结构83.2算法描述84调试与分析104.1调试过程101.2程序执行过程11参考文献12附录（关键部分程序清单）1317沈阳航空航天

2、大学课程设计报告1课程设计介绍1.1课程设计内容设计程序，建立带有父亲结点的平衡二叉树，系统主要功能是：从键盘上输入一整数序列，建立一颗平衡二叉树。1.2课程设计要求(1)要能够形象方便的观察树的结构；(2)要能够形象的演示树的平衡过程；(3)课程设计报告必须符合课程设计报告规范；(4)提交合格的报告后，经指导老师测试程序后，课设完成。17沈阳航空工业学院课程设计报告2课程设计原理2.1课设题目粗略分析根据课设题目要求，我将整体程序分为四大模块，这四个模块相互独立，没有任何嵌套调用的情况，以下是四个模块的大体

3、分析：(1)判断模块：在插入一个关键字时，首先先对该关键字进行判断，如果该关键字已经存在则不插入，否则插入该关键字，调用函数InsertAVL（）。(2)左子树插入模块：如果判断完的新关键字插在左子树上，则对该以指针p所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针p指向新的根结点，调用函数LeftProcess（）。(3)右子树插入模块：如果判断完的新关键字插在右子树上，则对该以指针p所指结点为根的二叉树作右平衡旋转处理，本算法结束时，指针p指向新的根结点，调用函数RightProcess（）。(4

4、)输出模块：对建立完成的平衡二叉树输出，输出格式为二叉树的括号表示，且每一步插入操作对应一次输出，最后做一次总体输出，调用函数，DispBSTree（）。2.2原理图介绍主函数主要实现的功能是函数调用，主函数首先对输入的关键字进行判断，调用函数InsertAVL（），若该关键字在已建树中已经存在，则返回主函数接着对下一个关键字进行判断。若该关键字在已建树中不存在，则插入该数，若插入左子树中则调用函数LeftProcess（）进行插入操作，若插入右子树中则调用函数DispBSTree（）进行插入操作。当所有的关

5、键字都插入完事之后，进行输出，调用函数，DispBSTree（）。2.2.1功能模块图1.判断模块17沈阳航空工业学院课程设计报告若在平衡二叉排序树b中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映b长高与否。2.左子树插入模块对以指针p所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针p指向新的根结点，插入分三种情况：原本左右子树等高，现因左子树增高而使树增；原本右子树比左子树高，现左右子树

6、等高；原本左子树比右子树高，须作左子树的平衡处理。若新关键字插入在*p的左孩子的左子树上，要做LL调整，若新关键字插入在*p的左孩子的右子树上，要做LR调整。3.右子树子树插入模块对以指针p所指结点为根的二叉树作右平衡旋转处理，本算法结束时，指针p指向新的根结点，插入分三种情况：原本左右子树等高，现因右子树增高而使树增；原本左子树比右子树高，现左右子树等高；原本右子树比左子树高，须作右子树的平衡处理。若新关键字插入在*p的右孩子的右子树上，要做RR调整，若新关键字插入在*p的右孩子的左子树上，要做RL调整。2

7、.2.2流程图分析1．主函数流程图主函数主要实现的功能是函数调用，主函数首先对输入的关键字进行判断，若该关键字在已建树中已经存在，则返回主函数接着对下一个关键字进行判断。若该关键字在已建树中不存在，则插入该数，当所有的关键字都插入完事之后，进行输出。流程图如图2.1所示。17沈阳航空工业学院课程设计报告图2.1主函数流程图2．判断模块流程图若在平衡二叉排序树b中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量tall

8、er反映b长高与否。流程图如图2.2所示。17沈阳航空工业学院课程设计报告图2.2判断模块流程图3．左子树插入模块流程图断完的新关键字插在左子树上，则对该以指针p所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针p指向新的根结针。流程图如图2.3所示。17沈阳航空工业学院课程设计报告图2.3左子树插入模块流程图4．右子树插入模块流程图断完的新关键字插在右子树上，则对该以指针p所指结点为根的二叉