1、 数 据 结 构 课 程 设 计 设计题目：二叉树的遍历及其相关结点的计算 学生姓名： 专业班级： 指导教师： 完成时间： 信 息 工 程 院 信息科学 系 目目 录录 第一章 课程与设计的目的与意义 . 1 1.1 课题设计目的 . 1 1.2 课题设计意义 . 1 第二章 需求分析 . 1 2.1 课程设计题目、任务及要求 1 2.2 课程设计思想 . 1 第三章 二叉树的基本概述 . 1 3.1 二叉树相关概念 . 1 3.2 二叉树的性质 . 2 3.3 二叉树的存储. 2 第四章：系统的概要设计 . 3 4.1 二叉树的生成过程 3 4.2 主要功能模块设计 3 第五章：系统详细设计
2、. 4 5.1 主函数菜单模块 . 4 5.2 二叉树的生成. 6 5.3 层次遍历模块. 8 5.4 求其相关结点的总数 10 第六章 测试结果 . 12 第七章 总结 14 第八章 参考文献 . 15 1 第一章第一章 课程与设计的目的与意义课程与设计的目的与意义 1.1 课题设计目的： （1） ：掌握数据结构分析设计思想及其存储表示方法和技术。 （2） ：掌握基于特定数据结构的基本运实现方法和设计。 （3） ：掌握工程化程序设计方法、技术及过程。 1.2 课题设计意义： （1） ：学会怎样团队协作去解决问题，增强自身的自信心、 主动性思考能力以及自主学习的能力。 （2） ：对课程设计这门
3、课有更深的了解，通过这次的课题设 计来提升对编程的兴趣，更加努力的学习这门课。 （3） ：通过课程设计的实践，在程序设计方法、上机操作等 基本技能和科学作风方面受到比较系统的严格训练。 第二章第二章 需求分析需求分析 2.1 课程设计题目、任务及要求 （1）对二叉树作各种遍历,输出结果； （2）求得二叉树结点的总数和叶子结点的数目； （3）要求二叉树的操作结果完整的输出 2.2 课程设计思想 （1）建立二叉树采用一个一个输入的方式。 （2）对二叉树分别实现多种遍历的方式。 （3）编写算法实现求结点和其叶子的数目。 第三章第三章 二叉树的基本概述二叉树的基本概述 3.1 二叉树相关概念 定义：二
4、叉树是 n（=0）个借点的有限集，它或者是空集（n=0） ，或者由 一个根结点及两颗互不相交的、分别称作这个根的左子树和右子树的二叉树组 成。 2 这也是一个递归定义。二叉树可以是空集，因此，根可以有空的左子树或右 子树，或者左、右子树皆为空。因此，二叉树有五种基本形态，如下图 1 所示： 图 3.1 二叉树的五种基本形态 满二叉树：一颗深度为 k 且有 2k-1 个结点的二叉树称为满二叉树。 完全二叉树：若一颗二叉树至多只有最下面的两层上结点的度数可以小于 2，并 且最下一层上的结点都集中在该层最左边的若干位置上， 则此二叉树称为完全二 叉树。 3.2 二叉树的性质 二叉树具有以下重要性质：
5、 性质 1 二叉树第 i 层上的结点数目最多为 2（i-1） （i=1） 。 性质 2 深度为 k 的二叉树至多有 2k-1（k=1）个结点。 性质 3 在任意一颗二叉树中，若终端结点的个数为 n0，度为 2 的结点数为 n2， 则 n0=n2+1。 性质 4 具有 n 个结点的完全二叉树的深度为log2n+1（或log2（n+1） ） 。 3.3 二叉树的存储 1.顺序存储结构 该方法是把二叉树的所有结点，按照一定的次序顺序，存储到一片连续的存 储单元中。因此，必须把结点安排成一个适当的线性序列，使得结点在这个序列 中的相互位置能反映出结点之间的逻辑关系。 2.链式存储结构 从上面的介绍可知
6、：顺序方式存储一般二叉树将浪费存储空间，并且若在树 中需要经常插入和删除结点时，由于大量地移动结点，顺序存储变的不可取。因 此，存储树的最自然的方法是链接的方法。二叉树的每个结点最多有两个孩子， 用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个 指针域 lchild 和 rchild，分别指向该结点的左孩子和右孩子，相应的类型说明 为： typedef char datatype; typedef struct node 3 datatype data; struct node *lchild,*rchild; bitree; 第四章：系统的概要设计第四章：系统的概要设计 4.1 二叉树的生成过程 二叉树的生成，采用逐个建立的方式，如图： 否 否 图 4.1 二叉树的生成过程 4.2 主要功能模块设计 程序主要设计了五个功能： 首先是创建二叉排序树， 完成后出现任务菜单， 菜单中设计了四个模块：退出，三种遍历，计算结点总数和叶子结点数目。 初始化数组
