课程设计---判断完全二叉树

《课程设计---判断完全二叉树》由会员分享，可在线阅读，更多相关《课程设计---判断完全二叉树（15页珍藏版）》请在毕设资料网上搜索。

1、 课程设计报告 课程名称：课程名称：数据结构课程设计 设计题目设计题目： 完全二叉树判断 系系 别：别： 计算机系 专专 业：业： 组组 别：别： 第三组 学生姓名学生姓名: : 学学 号号: 起止日期起止日期: 指导教师指导教师: - 1 - 目 录 第一章 需求分析. 2 1.1 课程设计任务及要求 2 1.2 课程设计思想及开发环境 2 第二章 概要设计. 3 2.1 总体方案 . 3 2.2 功能模块说明 . 3 第三章调试与操作说明 4 第四章课程设计总结与体会 4 第五章致谢 7 第六章参考文献 7 附录（源代码） 7 - 2 - 第一章 需求分析 1.1 课程设计任务及要求 该课

2、程设计的题目为：完全二叉树的判别。也就是对于输入的 二叉树进行判定，看是否为完全二叉树。 为实现此次课程设计的完成， 对程序设计作了相应的定义与限制。 首先， 为了输入的简洁，将树的结点树不大于 20；其次，对于二叉树的输入就按照 前序遍历的顺序进行输入；最后，对于程序的测试，应该从正反两面进行测 试，即输入一个是完全二叉树和一个不是完全二叉树的。 由于输入二叉树时， 对于不是完全二叉树的， 有的结点会没有左子树或右 子树，甚至两子树都没有，为跟好的表示没有子树的情况，在此次程序设计中用 “.”来表示 1.2 课程设计思想及开发环境 编写语言： C 语言 开发工具： Visual C+ Vis

3、ual Studio 6.0 VC+是微软公司开发的一个 IDE(集成开发环境)。学习 VC 要了解很多 Windows 平台的特性并且还要掌握 MFC、ATL、COM 等的知识， VC 基于 C， C+语言，主要由是 MFC 组成，是与系统联系非常紧密的编程工具，它兼有 高级，和低级语言的双重性，功能强大，灵活，执行效率高，几乎可说 VC 在 Windows 平台无所不能。 最大缺点是开发效率不高。 对于二叉树的构造，可以运用插入建立，还可以用递归建立。在此次设计中 运用的是递归建立。运用队列的进队函数进行对二叉树的结点的输入。对于进队 的第一个数据为二叉树的根结点，如果为非空，则继续输入第

4、二个进队元素，将 其设置为该根结点的左子树，然后将该左子树作为新的根结点，依次进行到下一 层的结点，直至到达叶节点（即既没有左子树也没有右子树） ，然后对于这以后 进队的元素则作为右子树，用相同的方法建树。 - 3 - 第二章概要说明 2.12.1 判定是否为完全二叉树的算法 判定完全二叉树，首先要知道什么是完全二叉树，对完全二叉树定义以 前，要明白满二叉树的定义。一棵深度为 k 且有 2 k-1 个结点的二叉树称为满二 叉树。对满二叉树的你借点进行连续编号，约定编号从根结点起，自上而下，自 左而右。由此引出完全二叉树的定义。深度为 k 的，右 n 个结点的二叉树，当且 仅当其每一个结点都与深度为 k 的满二叉树的编号从 1 至 n 的结点一一对应时， 称之为完全二叉树。所以对于二叉树的判定，假如某一结点有右子树但没有左子 树则该树不是完全二叉树。如果