数据结构课程设计-求二叉树的高度.doc

武汉理工大学数据结构课程设计说明书 学 号： 0121110860326课 程 设 计题 目数据结构（求二叉树的高度）学 院计算机科学与技术学院专 业 物联网工程班 级物联网1103班姓 名指导教师2013年7月1日课程设计任务书学生姓名： 孙雅川 专业班级： 物联网1103班 指导教师： 耿枫 工作单位： 计算机科学系 题 目: 计算二叉树高度 对任一棵二叉树计算并输出其高度.（1）利用教材6.3节所述的扩展前序二叉树序列建立二叉树。（2） 测试用例自己设计.要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第20周（6月29日至7月3日）完成。2、7月3 日8：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日 目录1.引言22.问题描述23.实验设计23.1.设计思想框图23.2.设计要点33.3具体设计33.3.1存储结构设计33.3.2主要算法设计33.3.3测试用例设计44.调试报告44.1出现问题：44.2解决办法55.源程序及测试结果56.算法优化及运行结果77.经验与体会8计算二叉树高度1.引言 数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。 数据结构是一门专业选技术基础课。一方面它要求我们学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应算法，并初步掌握算法的时间分析和空间分析的技术；另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求我们编写的程序结构清楚且正确易读，符合软件工程的规范，并培养我们的软件抽象能力。本次课程设计任务就是对二叉树的高度的求取。2.问题描述 已知任意一棵二叉树，求取它的高度并输出。 主要解决的问题：1.存储结构采用二叉链表，方便快捷 2.对子树深度求取的算法，主要采用递归算法3.实验设计3.1.设计思想框图 存储结构设计（二叉链表）创建二叉树（先序）二叉树深度算法（递归）主函数的编写3.2.设计要点 此次设计问题主要集中在求取二叉树的高度算法编写上，深度算法采用的是递归思想，对左右孩子不断求取高度，直到左、右孩子为空，再对左右孩子的高度进行比较，取两者中较大的加一作为二叉树的高度。3.3具体设计 3.3.1存储结构设计 线形表的顺序存储结构的特点是逻辑关系上相邻的两个元素物理位置上也相邻，因此可以随机存取表中任一元素。链式存储结构的特点是用一组任意的存储单元存储线形表的数据元素。因此在二叉树中采用二叉链表作为存储结构，操作简单而且不会浪费空间。 typedef struct tree/二叉树二叉链表存储结构的定义 char data; struct tree *lchild,*rchild;tree,*Tree; 3.3.2主要算法设计 1. void create(Tree &t)/创建一棵二叉树 char ch; ch=getchar(); if(ch=#) t=NULL; /如果子树为空，则用#表示 else t=(tree *)malloc(sizeof(tree); t-data=ch; create(t-lchild); create(t-rchild); 2.int deep(Tree &t)/深度算法 int ld=0,rd=0; if(!t) return 0; else ld=deep(t-lchild); rd=deep(t-rchild); if(ldrd) return rd+1; else return ld+1; 3.3.3测试用例设计 abcdfeg4.调试报告 4.1出现问题1. 创建二叉树时，没有对子树进行内存分配，导致程序运行后总是显示内存错误；2. 本次编程采用的是c语言，总是与c+混淆，导致语法错误；3. 编写深度算法时，未对左右子树ld、rd进行声明，导致错误；4. 编写深度算法时，在判断左右子树哪个更大时，判断条件写反了，导致编译成功后不能运行到深度算法这来；5. 编写头文件时，未将sring加入头文件里，导致sring类的都没有被声明。4.2解决办法 1.重新对子树进行内存分配 t=(tree *)malloc(sizeof(tree); 2.经过纠错后，将所有c+语言改成c语言； 3.重新对ld、rd进行声明 int ld=0,rd=0; 4.将判断条件改过后，即可正常运行 if(ldrd)； 5.经过检查后，将sring加入头文件 #include #include 5.源程序及测试结果 #include #include typedef struct tree/二叉树二叉链表存储结构的定义 char data; struct tree *lchild,*rchild;tree,*Tree; void create(Tree &t)/创建一棵二叉树 char ch; ch=getchar(); if(ch=#) t=NULL; /如果子树为空，则用#表示 else t=(tree *)malloc(sizeof(tree); t-data=ch; create(t-lchild); create(t-rchild); int deep(Tree &t)/深度算法 int ld=0,rd=0; if(!t) return 0; else ld=deep(t-lchild); rd=deep(t-rchild); if(ldlchild) ld+; deep(t-lchild,ld,rd); else if(t-rchild) rd+; deep(t-rchild,ld,rd); 2.void main()/主函数 Tree t; printf(按先序遍历输入二叉树，孩子为空用#号表示:n); create(t); int ld=0,rd=0; deep(t,ld,rd); printf(该二叉树的高度为:n); if(ldrd) printf(%dn,ld+1); else printf(%dn,rd+1); system(pause);7.经验与体会此次课程设计是对本学期数据结构学习成果的一个考察，也是对之前我们学过的c+的更高层次的运用，数据结构是建立在c+的基础上的，因此在本次试验中，我又重新翻阅了以前的课本用以加深理解。在本次课程设计中，我了解到自己在具体实现算法上仍有不足，能想得到算法的基本框图，但要把它真正实现出来仍需要依靠课本和同学的帮助，尤其是一些基本的地方，比如说头文件的创立、判定条件的编写、文件的声明、内存的分配，虽然大体上可以知道怎么做，但由于平时比较少进行实际操作，因此导致程序不断报错。因此以后还是要多进行上机操作，自己多动手编程，将课本上讲的