1、 学年论文学年论文（设计）（设计） （本科）（本科） 学 院 专 业 年 级 姓 名 论文（设计）题目 指导教师 职称 成 绩 2012 年 月 日 学号：学号： 2 摘要：摘要： 数据结构是一门研究非数值计算的程序设计问题中计算机的操 作对象以及它们之间的关系和操作的学科。 作为研究对象的数据结构 是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构在 计算机中的表示(又称映像)，称为数据的物理结构，又称存储结构。 相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。 本次课程设计， 程序中的数据采用 “树形结构” 作为其数据结构。 具体采用的是二叉树。 二叉树是树形结构的一个重
2、要的类型，二叉树 是 n(n0)个结点的有限集，它或者是空集(n0),或者由一个根结点 以及两棵互不相交的，分别称为左子树和右子树的二叉树组成。 二叉树的顺序存储结构是把二叉树所有结点， 按照一定的次序排 序，存储到一片连续的存储单元中。 但二叉树的顺序存储结构浪费空 间并且插入、删除不方便。二叉树的链式存储每个结点至少包含三个 域：数据域、左指针域、右指针域，不浪费空间。二叉树的存储结构 和算法比较简单，特别适合计算机处理，即使一般形式的树也可简单 的转换为二叉树。 现实中经常用到二叉树， 因此本课程设计主要实现了二叉树的建 立、三种遍历，计算二叉数的树深、统计叶子结点的个数等功能。 3 关
3、关键词：键词：二叉树；遍历；树深；叶子结点 学生签名： 2012 年 月 日 目录目录 一、需求分析 4 二、概要设计 5 三、详细设计 6 四、调试分析及测试 . 12 五、课程设计总结 . 20 参考文献 21 附录 . 21 4 二叉树二叉树基本操作基本操作 一、一、 需求分析需求分析 二叉树形象地说即树中每个节点最多只有两个分支， 它是一种重要的数据类 型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各 种机构的职位图表等。 二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历， 后序遍历。以及能够从输入的数据中得知二叉树的叶子结点的个数，二叉树的深 度
4、。在此，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。演示 程序以用户与计算机对话的方式进行，即在计算机终端上显示提示信息后，由用 户在键盘上输入相应动作的序号和相应的输入数据。 1.1 1.1 选题理由选题理由 根据自己的知识功底和能力水平择选了二叉树问题. 而且随着计算机技术 的飞速发展，越来越多的问题正逐渐改用计算机解答，并且有些技术已经非常成 熟。运用所学计算机知识来研究二叉树的有关内容可以锻炼和提高我编程 和独 立解决问题的能力，还可以使我增强信心，为我以后的编程开个好头，故我选择 了这个课题。 1.21.2 课程设计课程设计任务及要求任务及要求 (1)按先序次序输入二叉树
5、中结点的值,构造二叉链表表示的二叉树 t； (2)对二叉树 t 作先序、中序、后序遍历的递归算法,输出结果； (3)计算二叉树 t 的深度,输出结果； (4)计算二叉树 t 的叶子结点个数 1.31.3 课程设计思想课程设计思想 本次课程设计中，用到的主要知识就是递归思想，着重体会递归的思想。建 立二叉树采用先序次序插入的方式。对二叉树进行遍历时采用递归函数的方式。 求二叉树的深度及叶子结点个数均采用递归方式。 1.41.4 软硬件运行环境及开发工软硬件运行环境及开发工具具 5 WindowsXP 操作系统、Microsoft Visual C+ 6.0 二、二、 概要设计概要设计 2.12.
6、1 对程序中定义的核心数据结构及对其说明：对程序中定义的核心数据结构及对其说明： typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; 在开头定义了二叉树的链式存储结构，此处采用了每个结点中设置三个域， 即值域，左指针域和右指针域。 2.22.2 程序程序模块及其功能：模块及其功能： 本程序分为：7 大模块。二叉树的建立链式存储结构、前序遍历、中序遍历、 后序遍历、求叶子结点的个数计算、中序遍历、后序遍历、深度、主函数。 1、二叉树的建立链式存储结构；首先 typedef struct BiTNodetypedef struct BiTNode：定义二叉 树的链式存储结构， 此处采用了每个结点中设置三个域， datadata： 即值域， *lchild*lc
