按层次输入建立二叉树.doc

武汉理工大学数据结构课程设计说明书学 号： 0121310870710 课 程 设 计题 目按层次输入建立二叉树学 院计算机科学与技术专 业计算机科学与技术班 级计算机zy1302指导老师杨 克 俭姓 名朱 斌2014年12月17日 目 录1.课程设计任务书22按层次建立二叉树的实现32.1问题描述32.2开发平台32.3设计32.3.1存储结构设计32.3.2主要算法设计32.3.3测试用例设计52.4调试报告52.5经验和体会52.5.1算法改进（包括算法优、缺点，及其改进）52.5.2实验心得62.6源程序清单和运行结果63课内实践参考文献84课内实践评分标准91.课内实践任务书学生姓名： 朱 斌 专业班级： 计算机zy1302 指导教师： 杨 克 俭 工作单位： 计算机科学系 题 目: 按层次输入建立二叉树 初始条件：按层次输入扩展的完全二叉树中的结点，建立一棵二叉树。（1） 用二叉链表作存储结构；（2） 对建立的二叉树给出后序遍历的结果；（3） 自行设计测试用例；要求完成的主要任务: （包括课内实践工作量及其技术要求，以及说明书撰写等具体要求）课内实践报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1. 问题描述简述题目要解决的问题是什么。2. 设计存储结构设计、主要算法设计（用类C/C+语言或用框图描述）、测试用例设计；3. 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4. 经验和体会（包括对算法改进的设想）5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。说明：1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。2. 凡拷贝往年任务书或课内实践充数者，成绩一律无效，以0分记。时间安排：1第15周完成，验收时间为12月17日（星期三）上午2验收地点：实验中心3验收内容：可执行程序与源代码、课内实践报告书。指导教师签名： 2014年11月4日系主任（或责任教师）签名： 年 月 日2.按层次输入建立二叉树的实现2.1问题描述按层次输入建立一棵完全二叉树。（1）用二叉链表作存储结构；（2）对建立的二叉树给出后序遍历的结果；（3）测试用例自己设计；2.2开发平台系统：Windows-All语言选择：C+编译器版本：Visual C+ 6.02.3设计2.3.1存储结构设计由问题采用二叉链表存储结构为：typedef struct nodedatatype data;struct node *lchild, *rchild;bitree;bitree*creattree(); 2.3.2主要算法设计 （1）函数bitree*creattree()实现对二叉树的建立。定义结点编号为整型rear，且第一个顶点编号为1；结点数据域字符型ch，以#作为输入结束条件。同时使用指针数组bitree*Qmaxsize各项则指向依次建立的结点。 bitree*creattree()char ch;bitree*Qmaxsize;int front, rear;bitree*root, *s;root = NULL;front = 1; rear = 0;cout 按层次输入二叉树，以#结束输入： ch;while (ch!= #)rear+;s = new bitree;s-data = ch;s-lchild = s-rchild=NULL;Qrear = s;if (rear = 1)root = s;elseif (rear % 2 = 0)Qfront-lchild = s;else Qfront-rchild = s; front+; cin ch;return root; （2）函数void postorder(bitree*p)实现二叉树的后序遍历输出。 void postorder(bitree*p)if(p = NULL) return;elseif (p-lchild != NULL) postorder(p-lchild);if (p-rchild != NULL) postorder(p-rchild);cout data ; 2.3.3测试用例设计 假设建立一棵完全二叉树，按层次输入为:abcdefg#现按此程序建立二叉树按后序输出结果应为：d e b f g c a,则程序设计正确。2.4调试报告（1）指针数组maxsize设置较小，当结点数较多时，程序容易崩溃。（2）后序遍历输出时，缺少语句if(p = NULL) return;虽然编译时，没有语法错误；但是程序运行后明显无法满足题目要求。（3）最先建立二叉树时，输入采用ch=getchar()函数，每输入一个数据，点击一次回车，测试时就会出错；原因是getchar()函数能识别回车键作为一个字符；改正为采用cin输入，并且其不能识别空格、回车，输入时比较方便。2.5经验和体会2.5.1算法改进优点：算法设计的比较精简，占用存储空间较小，完全可以满足题目要求。缺点1：试验中的算法只适合于完全二叉树，不适用于一般二叉树。改进：可以把结点左子树或右子树为空的标记为一个特殊字符，然后输出二叉树广义表，即可显现二叉树结构。这样，程序可以适用于所有二叉树。缺点2：没有使用面向对象程序设计，没有使用类来维护数据的安全性。改进：使用类来封装数据成员和成员函数。2.5.2实验心得通过这次的课程设计，我发现在设计程序时，可以采用更加巧妙的方法达到同样的结果，这也是C+程序设计的魅力所在。但是，在实际实验时，会出现很多错误，有些甚至意想不到，可以通过查阅资料解决。因此，查阅资料是一项非常重要的能力。此外，选择正确、高效的算法技巧也十分重要，在满足要求的前提下，尽量减小时间、空间复杂度。充分考虑到各种情形，如变量的定义域，取值空间等，保持思维的严密性。同时，设计算法应该考虑可维护性、可重用性、用户友好性，严格按照格式编辑，可以节省很多时间，避免一些不必要的错误。相信通过这次课程设计，会对我以后的学习起到促进和补充的作用。2.6源程序清单和运行结果#includeusing namespace std;/二叉链表的结构类型定义const int maxsize = 1024;typedef char datatype;typedef struct nodedatatype data;struct node *lchild, *rchild;bitree;bitree*creattree();void postorder(bitree*);void main()bitree*pb;pb = creattree();postorder(pb);/二叉树的建立bitree*creattree()char ch;bitree*Qmaxsize;int front, rear; /rear为计数器，记录结点数bitree*root, *s;root = NULL;front = 1; rear = 0;cout 按层次输入二叉树，以#结束输入： ch;while (ch!= #)rear+;s = new bitree;s-data = ch;s-lchild = s-rchild=NULL;Qrear = s;if (rear = 1)root = s;elseif (rear % 2 = 0)Qfront-lchild = s;else Qfront-rchild = s; front+; cin ch;return root;/后序遍历输出二叉树void postorder(bitree*p)if(p = NULL) return;elseif (p-lchild != NULL) postorder(p-lchild);if (p-rchild != NULL) postorder(p-rchild);cout data ;运行结果截图：运行结果正确无误。3.课内实践参考资料1数据结构用面向对象方法与C+语言描述（第二版），殷人昆编著，清华大学出版社，出版或修订时间：2009年9月2数据结构(C语言版)，严蔚敏，吴伟民编著，出版社：清华大学出版社，出版或修订时间：1