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

1、 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目： 带父亲节点的平衡二叉树的带父亲节点的平衡二叉树的 建立建立 院（系）：计算机学院 专 业：网络工程 班 级： 学 号： 姓 名： 指导教师： I 目目 录录 1 1 课程设计介绍课程设计介绍 1 1.1 课程设计内容 . 1 1.2 课程设计要求 1 2 2 课程设计原理课程设计原理 2 2.1 课设题目粗略分析 . 2 2.2 原理图介绍 . 2 2.2.1 功能模块图 . 2 2.2.2 流程图分析 . 3 3 数据结构分析数据结构分析 8 3.1 存储结构 . 8 3.2 算法描述 .

2、8 4 4 调试与分析调试与分析 10 4.1 调试过程 . 10 1.2 程序执行过程 11 参考文献参考文献 12 附附 录（关键部分程序清单）录（关键部分程序清单） 13 1 1 1 课程设计介绍课程设计介绍 1.1 1.1 课程设计内容课程设计内容 设计程序，建立带有父亲结点的平衡二叉树，系统主要功能是：从键盘 上输入一整数序列，建立一颗平衡二叉树。 1.21.2 课程设计要求课程设计要求 (1) 要能够形象方便的观察树的结构； (2) 要能够形象的演示树的平衡过程； (3) 课程设计报告必须符合课程设计报告规范； (4) 提交合格的报告后，经指导老师测试程序后，课设完成。 2 2 2

3、 课程设计原理课程设计原理 2.1 2.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求，我将整体程序分为四大模块，这四个模块相互独立，没 有任何嵌套调用的情况，以下是四个模块的大体分析： (1)判断模块：在插入一个关键字时，首先先对该关键字进行判断，如果该关 键字已经存在则不插入，否则插入该关键字，调用函数 InsertAVL（） 。 (2)左子树插入模块：如果判断完的新关键字插在左子树上，则对该以指针 p 所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针 p 指向新的根结 点，调用函数 LeftProcess（） 。 (3)右子树插入模块：如果判断完的新关键字插在右子树上，则

4、对该以指针 p 所指结点为根的二叉树作右平衡旋转处理，本算法结束时，指针 p 指向新的根结 点，调用函数 RightProcess（） 。 (4)输出模块： 对建立完成的平衡二叉树输出， 输出格式为二叉树的括号表示， 且每一步插入操作对应一次输出，最后做一次总体输出，调用函数，DispBSTree （） 。 2 2. .2 2 原理图介绍原理图介绍 主函数主要实现的功能是函数调用，主函数首先对输入的关键字进行判断， 调用函数 InsertAVL（） ，若该关键字在已建树中已经存在，则返回主函数接着对 下一个关键字进行判断。若该关键字在已建树中不存在，则插入该数，若插入左 子树中则调用函数 LeftProcess（）进行插入操作，若插入右子树中则调用函数 DispBSTree（）进行插入操作。当所有的关键字都插入完事之后，进行输出，调 用函数，DispBSTree（） 。 2.2.1 2.2.1 功能模块图功能模块图 1.判断模块 3 若在平衡二叉排序树 b 中不存在和 e 有相同关键字的结点，则插入一个数据 元素为 e 的新结点，并返回 1，