![数据结构课程设计-带父亲节点的平衡二叉树的建立 (2).doc_第1页](http://file.renrendoc.com/FileRoot1/2019-7/18/1e8bb088-f536-4c87-a5a5-0c66fde0f29b/1e8bb088-f536-4c87-a5a5-0c66fde0f29b1.gif)
![数据结构课程设计-带父亲节点的平衡二叉树的建立 (2).doc_第2页](http://file.renrendoc.com/FileRoot1/2019-7/18/1e8bb088-f536-4c87-a5a5-0c66fde0f29b/1e8bb088-f536-4c87-a5a5-0c66fde0f29b2.gif)
![数据结构课程设计-带父亲节点的平衡二叉树的建立 (2).doc_第3页](http://file.renrendoc.com/FileRoot1/2019-7/18/1e8bb088-f536-4c87-a5a5-0c66fde0f29b/1e8bb088-f536-4c87-a5a5-0c66fde0f29b3.gif)
![数据结构课程设计-带父亲节点的平衡二叉树的建立 (2).doc_第4页](http://file.renrendoc.com/FileRoot1/2019-7/18/1e8bb088-f536-4c87-a5a5-0c66fde0f29b/1e8bb088-f536-4c87-a5a5-0c66fde0f29b4.gif)
![数据结构课程设计-带父亲节点的平衡二叉树的建立 (2).doc_第5页](http://file.renrendoc.com/FileRoot1/2019-7/18/1e8bb088-f536-4c87-a5a5-0c66fde0f29b/1e8bb088-f536-4c87-a5a5-0c66fde0f29b5.gif)
已阅读5页,还剩14页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
沈阳航空沈阳航空航天大学航天大学 课课 程程 设设 计计 报报 告告 课程设计名称:数据结构课程设计数据结构课程设计 课程设计题目:带父亲节点的平衡二叉树的带父亲节点的平衡二叉树的 建立建立 院(系):计算机学院 专 业:网络工程 班 级: 学 号: 姓 名:夏媛 指导教师:郑志勇 沈阳航空航天大学课程设计报告 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 算法描述8 4 4 调试与分析调试与分析.10 4.1 调试过程10 4.1 程序执行过程11 参考文献参考文献.12 附附 录(关键部分程序清单)录(关键部分程序清单).13 沈阳航空航天大学课程设计报告 1 1 1 课程设计介绍课程设计介绍 1.11.1 课程设计内容课程设计内容 设计程序,建立带有父亲结点的平衡二叉树,系统主要功能是:从键盘 上输入一整数序列,建立一颗平衡二叉树。 1.21.2 课程设计要求课程设计要求 (1) 要能够形象方便的观察树的结构; (2) 要能够形象的演示树的平衡过程; (3) 课程设计报告必须符合课程设计报告规范; (4) 提交合格的报告后,经指导老师测试程序后,课设完成。 沈阳航空工业学院课程设计报告 2 2 2 课程设计原理课程设计原理 2.12.1 课设题目粗略分析课设题目粗略分析 根据课设题目要求,我将整体程序分为四大模块,这四个模块相互独立,没 有任何嵌套调用的情况,以下是四个模块的大体分析: (1)判断模块:在插入一个关键字时,首先先对该关键字进行判断,如果该关 键字已经存在则不插入,否则插入该关键字,调用函数 insertavl() 。 (2)左子树插入模块:如果判断完的新关键字插在左子树上,则对该以指针 p 所指结点为根的二叉树作左平衡旋转处理,本算法结束时,指针 p 指向新的根 结点,调用函数 leftprocess() 。 (3)右子树插入模块:如果判断完的新关键字插在右子树上,则对该以指针 p 所指结点为根的二叉树作右平衡旋转处理,本算法结束时,指针 p 指向新的根 结点,调用函数 rightprocess() 。 (4)输出模块:对建立完成的平衡二叉树输出,输出格式为二叉树的括号表 示,且每一步插入操作对应一次输出,最后做一次总体输出,调用函数, dispbstree() 。 2.22.2 原理图介绍原理图介绍 主函数主要实现的功能是函数调用,主函数首先对输入的关键字进行判断, 调用函数 insertavl() ,若该关键字在已建树中已经存在,则返回主函数接着对 下一个关键字进行判断。若该关键字在已建树中不存在,则插入该数,若插入左 子树中则调用函数 leftprocess()进行插入操作,若插入右子树中则调用函数 dispbstree()进行插入操作。当所有的关键字都插入完事之后,进行输出,调 用函数,dispbstree() 。 .1 功能模块图功能模块图 1.判断模块 沈阳航空工业学院课程设计报告 3 若在平衡二叉排序树 b 中不存在和 e 有相同关键字的结点,则插入一个数据 元素为 e 的新结点,并返回 1,否则返回 0。若因插入而使二叉排序树失去平衡, 则作平衡旋转处理,布尔变量 taller 反映 b 长高与否。 2.左子树插入模块 对以指针 p 所指结点为根的二叉树作左平衡旋转处理,本算法结束时,指针 p 指向新的根结点,插入分三种情况:原本左右子树等高,现因左子树增高而使 树增;原本右子树比左子树高,现左右子树等高;原本左子树比右子树高,须作 左子树的平衡处理。若新关键字插入在*p 的左孩子的左子树上,要做 ll 调整, 若新关键字插入在*p 的左孩子的右子树上,要做 lr 调整。 3.右子树子树插入模块 对以指针 p 所指结点为根的二叉树作右平衡旋转处理,本算法结束时,指针 p 指向新的根结点,插入分三种情况:原本左右子树等高,现因右子树增高而使 树增;原本左子树比右子树高,现左右子树等高;原本右子树比左子树高,须作 右子树的平衡处理。若新关键字插入在*p 的右孩子的右子树上,要做 rr 调整, 若新关键字插入在*p 的右孩子的左子树上,要做 rl 调整。 .2 流程图分析流程图分析 1主函数流程图 主函数主要实现的功能是函数调用,主函数首先对输入的关键字进行判断, 若该关键字在已建树中已经存在,则返回主函数接着对下一个关键字进行判断。 若该关键字在已建树中不存在,则插入该数,当所有的关键字都插入完事之后, 进行输出。流程图如图 2.1 所示。 沈阳航空工业学院课程设计报告 4 开始 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; ekey y leftprocess(b,taller) n 结束 rightprocess(b,taller) 图 2.2 判断模块流程图 3左子树插入模块流程图 断完的新关键字插在左子树上,则对该以指针 p 所指结点为根的二叉树作左 平衡旋转处理,本算法结束时,指针 p 指向新的根结针。流程图如图 2.3 所示。 沈阳航空工业学院课程设计报告 6 开始 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=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 所指结点为根的二叉树作右 平衡旋转处理,本算法结束时,指针 p 指向新的根结针。流程图如图 2.4 所示。 沈阳航空工业学院课程设计报告 7 开始 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-rchild; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; p1-bf=1 y p=p2; p-bf=0; taller=0 结束 图 2.4 右子树插入模块流程图 沈阳航空工业学院课程设计报告 8 3 数据结构分析数据结构分析 3.13.1 存储结构存储结构 定义一个关键字类型的字符数组,其空间足够大,用来存放关键字。 3.23.2 算法描述算法描述 1判断关键字算法如下: /若在平衡二叉排序树 b 中不存在和 e 有相同关键字的结点,则插入一个 数据元素为 e 的新结点, if(b=null) /原树为空,插入新结点,树长高,置 taller 为 1 b=(bstnode*)malloc(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-rchild,e,taller)=0) /未插入 return 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 /原本左子树比右子树高,须作左子树的平衡处理 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; 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. 对二叉树的左右子树进行插入调整的操作时,由于考虑问题不够全面而 导致输出结果出现错误,在查质料重新学习二叉树后,解决了此问题。 沈阳航空工业学院课程设计报告 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.北京:中国轻工业出版社,2004. 沈阳航空工业学院课程设计报告 13 附附 录(关键部分程序清单)录(关键部分程序清单) 程序代码程序代码 #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-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; 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; 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) 沈阳航空工业学院课程设计报告 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-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); 沈阳航空工业学院课程设计报告 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,7,8,9,n=10; printf(“创建一棵 avl 树:n“); for(i
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 产品服务质量保证承诺书模板
- 机器人促销方案策划(2篇)
- 智能机器人促销方案(2篇)
- 防火安全整改方案(2篇)
- 挑战49 河北卷(河北近四年共30题)(原卷版)-2022年中考物理真题《压轴挑战》分类汇编
- 水稻新品种、新组合项目可行性报告
- 《基础会计》 课件 第四章 制造业企业主要经济业务的核算(二)
- 家居空间设计项目可行性报告
- 空气和废气监测仪器项目可行性报告
- 雪国读后感 可编辑
- 2024年山西省无人机测绘操控员竞赛备考试题库(含各题型)
- 篮球直播策划方案公司
- 新时代女性的风采
- 钢材供货培训方案
- 旅投公司公开招聘笔试题
- 旅游推广短视频创作方案
- 新生儿护理拍嗝课件
- 2023年民族团结一家亲工作总结6篇
- 弱电安全环保施工方案
- 2024-2024年全国初中化学竞赛试卷及答案-副本
- 专业人力资源顾问服务协议
评论
0/150
提交评论