数据结构课程设计--完全二叉树的判别

《数据结构课程设计--完全二叉树的判别》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、广州大学松田学院《数据结构》课程设计学号：广州大学松田学院数据结构课程设计题目完全二叉树的判别专业班级姓名指导教师年月日广州大学松田学院《数据结构》课程设计广州大学松田学院《数据结构》课程设计课程设计任务书学生姓名：专业班级：指导教师：严宇工作单位：广州大学松田学院题目:完全二叉树的判别初始条件：试写一个判别给定二叉树是否为完全二叉树的程序。（1）此二叉树以二叉链表作存储结构；（2）自行设计正、反测试用例；要求完成的主要任务:课程设计报告按学校规定格式用A4纸打印，并应包含如下内容：1.问题描述简述题

2、目要解决的问题是什么。2.设计存储结构设计、主要算法设计（用C语言或用框图描述）、测试用例设计。3.调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4.程序运行结果（包括对算法改进的设想）5.经验与体会6.参考文献说明：1.设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第17周完成。2、2011年6月28号提交打印版课程设计，源程序刻录光盘。指导教师签名：年月日广州大学松田学院《数据结构》课程设计目录1.问题分析与任务定义2.数据类型和系统设计

3、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、问题分析与任务定义该课程设计的题目为：完全二叉树的判别。也就是对于输入的二叉树进行判定，看是否为完全二叉树。为实现此次课程设计的完成，对程序设计作了相应的定义与限制。首先，为了输入的简洁，将树的结点树不

4、大于20；其次，对于二叉树的输入就按照前序遍历的顺序进行输入；最后，对于程序的测试，应该从正反两面进行测试，即输入一个是完全二叉树和一个不是完全二叉树的。由于输入二叉树时，对于不是完全二叉树的，有的结点会没有左子树或右子树，甚至两子树都没有，为跟好的表示没有子树的情况，在此次程序设计中用“@”来表示。对于此次的正反测试，分别用一下的两个二叉树进行测试：a)完全二叉树b)非完全二叉树所以输入的顺序分别为：正面测试：abd@@e@@cf@@@；反面测试：abd@@@ce@@f@@。2、数据类型和系统设计2

5、.1储存结构设计根据设计的要求，对于本程序的储存结构要用二叉链表。以下是作为本次设计数据的存储结构的定义：templateclassbinarytree;templateclasstreenode广州大学松田学院《数据结构》课程设计{friendclassbinarytree;private:type1data;treenode*leftchild;treenode*rightchild;public:treen

6、ode():leftchild(NULL),rightchlid(NULL){}treenode(type1item,treenode*left=NULL,treenode*right=NULL):data(item),leftchild(left),rightchild(right){}type1getdata()const{returndata;}treenode*getleft()const{returnleftchlid;}treenode

7、>*getright()const{returnrightchlid;}voidsetdata(consttype1&item){data=item;}voidsetleft(treenode*left){leftchild=left;}voidsetright(treenode*right){rightchild=right;}};2.2主要算法设计2.2.1二叉树构造的算法对于二叉树的构造，可以运用插入建立，还可以用递归建立。在此次设计中运用的是递归建立。运用队列的进队

8、函数进行对二叉树的结点的输入。对于进队的第一个数据为二叉树的根结点，如果为非空，则继续输入第二个进队元素，将其设置为该根结点的左子树，然后将该左子树作为新的根结点，依次进行到下一层的结点，直至到达叶节点（即既没有左子树也没有右子树），然后对于这以后进队的元素则作为右子树，用相同的方法建树。2.2.2判定是否为完全二叉树的算法广州大学松田学院《数据结构》课程设计判定完全二叉树，首先要知道什么是完全二叉树，对完全二叉树定义以前，要明白满二叉树的定义。一棵深度