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

《数据结构课程设计带父亲节点的平衡二叉树的建立.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计带父亲节点的平衡二叉树的建立.doc（19页珍藏版）》请在三一文库上搜索。

1、XXX 航空航空航天大学航天大学 课课 程程 设设 计计 报报 告告 课程设计名称：数据结构课程设计数据结构课程设计 课程设计题目：带父亲节点的平衡二叉树的带父亲节点的平衡二叉树的 建立建立 院（系）：计算机学院 专 业：网络工程 班 级： 学 号： 姓 名： 指导教师： 目目 录录 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 算法描述.8

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

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

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

5、操作，若插入右子树中则调用函数 DispBSTree（）进行插入操作。当所有的关键字都插入完事之后，进行输出，调 用函数，DispBSTree（） 。 2.2.12.2.1 功能模块图功能模块图 1.判断模块 若在平衡二叉排序树 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.22.2.2 流程图分析流程图分析 1主函数流程图 主函数主要实现的功能是函数调用，主函数首先对输入的关键字进行判断， 若该关键字在已建树中已经存在，则返回主函数接着对下一个关键字进行判断。 若该关键字在已建树中不存在，则插入该数，当所有的关键字都插入完事之后， 进行输出。流程图如图 2.1 所示。 开始 BSTNode *b=NULL; int i,j; KeyType a=6,1,2,3,4,5,0,7,8,9,n=10; Y key存在 Y InsertAVL(b,ai,j); DispBSTree(b); N for(i=0;ikey Y taller=0; return 0; e

8、key Y LeftProcess(b,taller) N 结束 RightProcess(b,taller) 图 2.2 判断模块流程图 3左子树插入模块流程图 断完的新关键字插在左子树上，则对该以指针 p 所指结点为根的二叉树作左 平衡旋转处理，本算法结束时，指针 p 指向新的根结针。流程图如图 2.3 所示。 开始 BSTNode *p1,*p2 BSTNode * Y N Y N Y p-bf=0 p-bf=1; taller=1 p-bf=-1 p-bf=0; taller=0 p1-bf=1 N p1=p-lchild; p-lchild=p1-rchild; p1-rchild=

9、p; p-bf=p1-bf=0; p=p1; p-bf=p1-bf=0 p2-bf=0 Y N p2-bf=1 N Y p1-bf=0; p-bf=-1 N p1-bf=1; p-bf=0; p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; p1-bf=-1 Y taller=0p=p2; p-bf=0; ; taller=0 结束 图 2.3 左子树插入模块流程图 4右子树插入模块流程图 断完的新关键字插在右子树上，则对该以指针 p 所指结点为根的二叉树作右 平衡旋转处理，本算法

10、结束时，指针 p 指向新的根结针。流程图如图 2.4 所示。 开始 BSTNode *p1,*p2 BSTNode * Y N Y N Y p-bf=-1 p-bf=1; taller=1 p-bf=1 p-bf=0; taller=0 1-bf=-1 N p1=p-rchild p-rchild=p1-lchild; p1-lchild=p; p-bf=p1-bf=0; p=p1; p-bf=p1-bf=0; p2-bf=0 Y N p2-bf=-1 N Y p1-bf=0; p-bf=1 N p1-bf=-1; p-bf=0 p2=p1-lchild; p1-lchild=p2-rchil

11、d; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; p1-bf=1 Y p=p2; p-bf=0; taller=0 结束 图 2.4 右子树插入模块流程图 3 数据结构分析数据结构分析 3.13.1 存储结构存储结构 定义一个关键字类型的字符数组，其空间足够大，用来存放关键字。 3.23.2 算法描述算法描述 1判断关键字算法如下： /若在平衡二叉排序树 b 中不存在和 e 有相同关键字的结点，则插入一个 数据元素为 e 的新结点， if(b=NULL) /原树为空，插入新结点，树长高，置 taller 为 1 b=(BSTNode*)mall

12、oc(sizeof(BSTNode); b-key=e; b-lchild=b-rchild=NULL; b-bf=0; taller=1; else if(e=b-key) /树中已存在和 e 有相同关键字的结点则不插入 taller=0; return 0; if(ekey) /继续在*b 的左子树中进行搜索 if(InsertAVL(b-lchild,e,taller)=0) /未插入 return 0; if(taller=1) /已插入到*b 的左子树中且左子树长高 LeftProcess(b,taller); else /继续在*b 的右子树中进行搜索 if(InsertAVL(b

13、-rchild,e,taller)=0) /未插入 return 0; if(taller=1) /已插入到*b 的右子树中且右子树长高 RightProcess(b,taller); return 1; 2.左平衡处理算法如下： /对以指针 p 所指结点为根的二叉树作左平衡旋转处理，本算法结束时， /指针 p 指向新的根结点 BSTNode *p1,*p2; if(p-bf=0) /原本左右子树等高，现因左子树增高而使树增高 p-bf=1; taller=1; else if(p-bf=-1) /原本右子树比左子树高，现左右子树等高 p-bf=0; taller=0; else /原本左子树

14、比右子树高，须作左子树的平衡处理 p1=p-lchild; /p 指向*p 的左子树根节点 if(p1-bf=1) /新结点插入在*p 的左孩子的左子树上，要做 LL 调整 p-lchild=p1-rchild; p1-rchild=p; p-bf=p1-bf=0; p=p1; else if(p1-bf=-1) /新结点插入在*p 的左孩子的右子树上，要做 LR 调整 p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) /新结点插入在*p2 处作为叶子结点的

15、情况 p-bf=p1-bf=0; else if(p2-bf=1) /新结点插在*p2 的左子树上的情况 p1-bf=0; p-bf=-1; else /新结点插在*p2 的右子树上的情况 p1-bf=1; p-bf=0; p=p2; p-bf=0; /仍将 p 指向新的根结点，并置其 bf 值为 0 taller=0; 4 4 调试与分析调试与分析 4.14.1 调试过程调试过程 在调试程序是主要遇到一下几类问题： 1. 本程序用到指针的地方特别多，由于指针那部分知识我掌握的不是很好， 故而在这方面有困难。后来我通过在图书馆查资料、看书解决了这方面问题。 2. 对二叉树的左右子树进行插入调整

16、的操作时，由于考虑问题不够全面而 导致输出结果出现错误，在查质料重新学习二叉树后，解决了此问题。 4.1 程序执行过程程序执行过程 图 4.1 第一组输入执行结果 图 4.2 第二组输入执行结果 参考文献参考文献 1 严蔚敏.吴伟民. .数据结构M.北京：清华大学出版社，2007. 2 张长海.陈娟. .C 程序设计M.北京：高等教育出版社，2004. 3 谭浩强. .C 程序设计M.北京：清华大学出版社，2005. 4 徐孝凯.数据结构实用教程.M.北京：清华大学出版社，2006. 5 张秉权. .数据结构（C 语言描述）.M.北京：中国轻工业出版社，2004. 附附 录（关键部分程序清单）

17、录（关键部分程序清单） 程序代码程序代码 #include #include typedef int KeyType typedef struct node KeyType key; int bf; struct node *lchild,*rchild; BSTNode; void LeftProcess(BSTNode * if(p-bf=0) p-bf=1; taller=1; else if(p-bf=-1) p-bf=0; taller=0; else p1=p-lchild if(p1-bf=1) p-lchild=p1-rchild; p1-rchild=p; p-bf=p1-b

18、f=0; p=p1; else if(p1-bf=-1) p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) p-bf=p1-bf=0; else if(p2-bf=1) p1-bf=0; p-bf=-1; else p1-bf=1; p-bf=0; p=p2; p-bf=0; taller=0; void RightProcess(BSTNode * if(p-bf=0) p-bf=-1; taller=1; else if(p-bf=1) p-bf=0;

19、taller=0; else p1=p-rchild; if(p1-bf=-1) p-rchild=p1-lchild; p1-lchild=p; p-bf=p1-bf=0; p=p1; else if(p1-bf=1) p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; if(p2-bf=0) p-bf=p1-bf=0; else if(p2-bf=-1) p1-bf=0; p-bf=1; else p1-bf=-1; p-bf=0; p=p2; p-bf=0; taller=0;

20、 int InsertAVL(BSTNode* b-key=e; b-lchild=b-rchild=NULL; b-bf=0; taller=1; else if(e=b-key) taller=0; return 0; if(ekey) if(InsertAVL(b-lchild,e,taller)=0) return 0; if(taller=1) LeftProcess(b,taller); else if(InsertAVL(b-rchild,e,taller)=0) return 0; if(taller=1) RightProcess(b,taller); return 1; v

21、oid DispBSTree(BSTNode *b) /*以括号表示法输出 AVL*/ if(b!=NULL) printf(%d,b-key); if(b-lchild!=NULL|b-rchild!=NULL) printf(); DispBSTree(b-lchild); if(b-rchild!=NULL)printf(,); DispBSTree(b-rchild); printf(); int main() BSTNode *b=NULL; int i,j; KeyType a=6,1,2,3,4,5,0,7,8,9,n=10; printf(创建一棵 AVL 树:n); for(

22、i=0;in;i+) printf(第%d 步，插入%d 元素:,i+1,ai); InsertAVL(b,ai,j); DispBSTree(b); printf(n); printf(AVL:); DispBSTree(b); printf(n); return 0; 课程设计总结： 本次课程设计的完满成功，是我认识到自己的不足，不仅是对知识的不足 还有我个人性格的不足。对此，谢谢郑志勇老师的认真指导，我会在以后的学 习中好好学习、正确学习，真正的是自己学到知识。 本次课程设计，巩固了以前学过的 C 语言的知识，在这次课程设计中我体 会到 C 语言超强的逻辑性，能够熟练使用 VC+的编译环

23、境，也对这两门课程有 了新的认识，他们既有联系，又相互区别，在编写程序过程中要灵活应用。对 数据结构的理解有待加强，算法的知识面也有待于提高。不同的人会选择不同 的算法，所以即使同样的程序，不同的人必然会设计出不同的方案，所以以后 的学习生活中，一定要广泛涉猎，掌握更多更好的解决问题的方法。 通过这次的课程设计使我了解到，只掌握理论的知识是不够的，课堂上的 知识仅仅是理论，并且书本太狭隘，我们以后的学习不应该再局限于书本，必 须要把理论和实际相结合起来，得让所学的知识能在实际当中应用才是做到了 学以致用，才能把所学的东西具体化，体现出知识的重要。并且，只有做到了 学以致用，才能让我们对知识有更进一步的了解，才能更好的掌握知识。通过 这次的课程设计使我积累了很多的经验，同时也让我了解到了自己在学习上的 不足，通过以后的学习来弥补这些不足。 1. 指导教师评语： 指导教师(签字)： 年 月 日 课程设计成绩