课程设计任务书--完全二叉树的判别.doc

课程设计任务书 学生姓名： 专业班级： 工作单位： 计算机科学系 题 目:完全二叉树的判别 初始条件： 试写一个判别给定二叉树是否为完全二叉树的程序。 （1）此二叉树以二叉链表作存储结构； （2）自行设计正、反测试用例； 要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1. 问题描述 简述题目要解决的问题是什么。 2. 设计 存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计； 3. 调试报告 调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。 4. 经验和体会（包括对算法改进的设想） 5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。 说明： 1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。 2. 凡拷贝往届任务书或课程设计充数者，成绩一律无效，以0分记。 时间安排： 1、第18周完成。 2、7月2日8:30时到实验中心检查程序、交课程设计报告、源程序（U盘）。 指导教师签名： 2010年6月22日 系主任（或责任教师）签名： 年 月 日 目录 1.问题分析与任务定义 2.数据类型和系统设计 2.1储存结构设计 2.2主要算法设计 2.2.1二叉树构造的算法 2.2.2判定是否为完全二叉树的算法 2.2.3测试用例设计 2.2.4程序各模块之间的关系图 3.程序调试 3.1.对设计和编码的讨论和分析 3.2调试 4.程序运行结果 5.经验与体会 6.参考文献 完全二叉树的判别 1、问题分析与任务定义 该课程设计的题目为：完全二叉树的判别。也就是对于输入的 二叉树进行判定，看是否为完全二叉树。 为实现此次课程设计的完成，对程序设计作了相应的定义与限制。首先，为了输入的简洁，将树的结点树不大于20；其次，对于二叉树的输入就按照前序遍历的顺序进行输入；最后，对于程序的测试，应该从正反两面进行测试，即输入一个是完全二叉树和一个不是完全二叉树的。 由于输入二叉树时，对于不是完全二叉树的，有的结点会没有左子树或右子树，甚至两子树都没有，为跟好的表示没有子树的情况，在此次程序设计中用“@”来表示。 对于此次的正反测试，分别用一下的两个二叉树进行测试： a) 完全二叉树 b) 非完全二叉树 所以输入的顺序分别为： 正面测试：a b d @ @ e @ @ c f @ @ @ ； 反面测试：a b d @ @ @ c e @ @ f @ @ 。 2、数据类型和系统设计 2.1储存结构设计 根据设计的要求，对于本程序的储存结构要用二叉链表。 以下是作为本次设计数据的存储结构的定义： template class type1class binarytree; templateclass type1 class treenode { friend class binarytreetype1; private: type1 data; treenodetype1* leftchild; treenodetype1* rightchild; public: treenode():leftchild(NULL),rightchlid(NULL){} treenode(type1 item,treenodetype1*left=NULL, treenodetype1*right=NULL):data(item), leftchild(left),rightchild(right){} type1 getdata()const {return data;} treenodetype1* getleft()const {return leftchlid;} treenodetype1*getright()const {return rightchlid;} void setdata(const type1 item){ data=item;} voidsetleft(treenodetype1*left){leftchild=left;}