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

1、 课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计数据结构课程设计课程设计题目：带父亲节点的平衡二叉树的带父亲节点的平衡二叉树的建立建立院（系）：计算机学院专 业：网络工程班 级：学 号：姓 名： 指导教师： 沈阳航空航天大学课程设计报告 i 目目 录录1 1 课程设计介绍课程设计介绍.11.1 课程设计内容.11.2 课程设计要求.12 2 课程设计原理课程设计原理.22.1 课设题目粗略分析.22.2 原理图介绍.22.2.1 功能模块图.22.2.2 流程图分析.33 数据结构分析数据结构分析.83.1 存储结构.83.2 算法描述.84 4 调试与分析调试与分析.104

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

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

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

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

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

7、1主函数流程图主函数主要实现的功能是函数调用，主函数首先对输入的关键字进行判断，若该关键字在已建树中已经存在，则返回主函数接着对下一个关键字进行判断。若该关键字在已建树中不存在，则插入该数，当所有的关键字都插入完事之后，进行输出。流程图如图 2.1 所示。沈阳航空工业学院课程设计报告 4 开始bstnode *b=null; int i,j;keytype a=6,1,2,3,4,5,0,7,8,9,n=10;ykey存在yinsertavl(b,ai,j); dispbstree(b);nfor(i=0;ikeyytaller=0; return 0;ekeyy leftprocess(b,

8、taller)n结束rightprocess(b,taller)图 2.2 判断模块流程图3左子树插入模块流程图 断完的新关键字插在左子树上，则对该以指针 p 所指结点为根的二叉树作左平衡旋转处理，本算法结束时，指针 p 指向新的根结针。流程图如图 2.3 所示。沈阳航空工业学院课程设计报告 6 开始bstnode *p1,*p2bstnode *&p,int &taller;ynynyp-bf=0p-bf=1; taller=1p-bf=-1p-bf=0; taller=0p1-bf=1np1=p-lchild;p-lchild=p1-rchild; p1-rchild=p; p-bf=p1

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

10、。沈阳航空工业学院课程设计报告 7 开始bstnode *p1,*p2bstnode *&p,int &taller;ynynyp-bf=-1p-bf=1; taller=1p-bf=1p-bf=0; taller=01-bf=-1np1=p-rchildp-rchild=p1-lchild; p1-lchild=p; p-bf=p1-bf=0; p=p1;p-bf=p1-bf=0;p2-bf=0ynp2-bf=-1nyp1-bf=0; p-bf=1np1-bf=-1; p-bf=0p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchil

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

12、key=e; b-lchild=b-rchild=null; b-bf=0; taller=1;elseif(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-rchild,e,taller)=0) /未插入 retu

13、rn 0; if(taller=1) /已插入到*b 的右子树中且右子树长高 沈阳航空工业学院课程设计报告 9 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 处作为叶子结点的情况 p-bf=p1-bf=0

15、; else if(p2-bf=1) /新结点插在*p2 的左子树上的情况沈阳航空工业学院课程设计报告 10 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、时，由于考虑问题不够全面而导致输出结果出现错误，在查质料重新学习二叉树后，解决了此问题。沈阳航空工业学院课程设计报告 11 4.1 程序执行过程程序执行过程图 4.1 第一组输入执行结果图 4.2 第二组输入执行结果沈阳航空工业学院课程设计报告 12 参考文献参考文献1 严蔚敏.吴伟民. .数据结构m.北京：清华大学出版社，2007.2 张长海.陈娟. .c 程序设计m.北京：高等教育出版社，2004. 3 谭浩强. .c 程序设计m.北京：清华大学出版社，2005.4 徐孝凯.数据结构实用教程.m.北京：清华大学出版社，2006.5 张秉权. .数据结构（c 语言描述）.m.北京：中国轻工业

17、出版社，2004.沈阳航空工业学院课程设计报告 13 附附 录（关键部分程序清单）录（关键部分程序清单）程序代码程序代码#include#includetypedef int keytypetypedef struct nodekeytype key; int bf; struct node *lchild,*rchild;bstnode;void leftprocess(bstnode *&p,int &taller) /*对以指针 p 所指结点为根的二叉树作左平衡旋转处理，本算法结束时指针 p 指向新结点*/ bstnode *p1,*p2; if(p-bf=0) p-bf=1; tall

18、er=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-bf=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)沈阳航空工业学院课程设计报告 14 p1-bf=0; p-bf=-1;

19、 else p1-bf=1; p-bf=0; p=p2; p-bf=0; taller=0; void rightprocess(bstnode *&p,int &taller) /*对以指针 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 p1=p-rchild; if(p1-bf=-1) p-rchild=p1-lchild; p1-lchild=p; p-bf=p1-bf=0; p

20、=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)沈阳航空工业学院课程设计报告 15 p1-bf=0; p-bf=1; else p1-bf=-1; p-bf=0; p=p2; p-bf=0; taller=0; int insertavl(bstnode*&b,keytype e,int &taller) /*若在平衡二叉排序树 b 中不存在和 e 有

21、相同关键字的结点，则插入一个数据元素为 e 的新结点，并返回 1，否则返回 0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变 taller反映 b 长高与否*/ if(b=null)b=(bstnode*)malloc(sizeof(bstnode); b-key=e; b-lchild=b-rchild=null; b-bf=0; taller=1;elseif(e=b-key)taller=0; return 0;if(ekey)if(insertavl(b-lchild,e,taller)=0) return 0;if(taller=1) leftprocess(b,tall

22、er);else if(insertavl(b-rchild,e,taller)=0) return 0; if(taller=1) rightprocess(b,taller);沈阳航空工业学院课程设计报告 16 return 1;void 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,