1、 2015 届课程设计 完全二叉树的判断完全二叉树的判断 课程设计论文课程设计论文 学生姓名 学 号 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 计算机 指导教师 教师职称 讲师 第 - 1 - 页 共 17 页 目目 录录 前言 1 正文 2 2.1 课程设计任务及要求 2 2.2 课程设计思想 2 2.3 判定是否为完全二叉树的算法 2 2.4 功能模块说明 3 2.5 编码设计 4 2.6 调试 5 2.7 程序运行结果 6 课程设计总结 9 参考文献 . 10 附录 . 11 前言前言 在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子 树”
2、 （left subtree）和“右子树” （right subtree） 。二叉树常被用作二叉查找树和二叉堆或是二 叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点)，二叉树的子树有左右之 第 - 2 - 页 共 17 页 分， 次序不能颠倒。 二叉树的第 i 层至多有 2 的 i -1 次方个结点； 深度为 k 的二叉树至多有 2(k) -1 个结点；对任何一棵二叉树 T，如果其终端结点数(即叶子结点数)为 n0，度为 2 的结点数为 n2， 则 n0 = n2 + 1。 二叉树也是递归定义的，其结点 有左右子树之分，逻辑上二叉树有五种 基本形态： (1)空二叉树(a)
3、； (2)只有一个根结点的二叉树 (b)； (3)只有左子树(c)； (4)只有右子树(d)； (5)完全二叉树(e) 完全二叉树： 若设二叉树的高度为 h， 除第 h 层外， 其它各层 (1h-1) 的结点数都达到最大个数， 第 h 层 有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。 满二叉树 除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。 深度: 二叉树的层数，就是高度。 先序遍历： 先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右） 。 首 先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后
4、 遍历左子树，最后遍历右子树，如果二叉树为空则返回。 例如，下图所示二叉树的遍历结果是：ABDECF 正文正文 2.1 课程设计任务及要求 该课程设计的题目为：完全二叉树的判别。也就是对于输入的 二叉树进行判定，看是否为完全二叉树。 为实现此次课程设计的完成，对程序设计作了相应的定义与限制。首先，为了输入的简洁，将 树的结点树不大于 20；其次，对于二叉树的输入就按照前序遍历的顺序进行输入；最后，对于程 序的测试，应该从正反两面进行测试，即输入一个是完全二叉树和一个不是完全二叉树的。 由于输入二叉树时，对于不是完全二叉树的，有的结点会没有左子树或右子树，甚至两子树都 第 - 3 - 页 共 1
5、7 页 没有，为跟好的表示没有子树的情况，在此次程序设计中用“.”来表示. 在计算机科学中， 二叉树是每个结点最多有两个子树的有序树。 通常子树的根被称作 “左子树” （left subtree）和“右子树” （right subtree） 。二叉树常被用作二叉查找树和二叉堆或是二叉 排序树。 二叉树的每个结点至多只有二棵子树(不存在度大于 2 的结点)， 二叉树的子树有左右之分， 次序不能颠倒。二叉树的第 i 层至多有 2 的 i -1 次方个结点；深度为 k 的二叉树至多有 2(k) -1 个结点；对任何一棵二叉树 T，如果其终端结点数(即叶子结点数)为 n0，度为 2 的结点数为 n2，
6、 则 n0 = n2 + 1。 2.2 课程设计思想 对于二叉树的构造， 可以运用插入建立， 还可以用递归建立。 在此次设计中运用的是递归建立。 运用队列的进队函数进行对二叉树的结点的输入。对于进队的第一个数据为二叉树的根结点，如果 为非空，则继续输入第二个进队元素，将其设置为该根结点的左子树，然后将该左子树作为新的根 结点，依次进行到下一层的结点，直至到达叶节点（即既没有左子树也没有右子树） ，然后对于这 以后进队的元素则作为右子树，用相同的方法建树。 2.3 判定是否为完全二叉树的算法 判定完全二叉树，首先要知道什么是完全二叉树，对完全二叉树定义以前，要明白满二叉树的 定义。一棵深度为 k 且有 2 k-1 个结点的二叉树称为满二叉树。对满二叉树的你借点进行连续编号， 约定编号从根结点起，自上而下，自左而右。由此引出完全二叉树的定义。深度为 k 的，右 n 个结 点的二叉树，当且仅当其每一个结点都与深度为 k
