湖南涉外经济学院
课程设计报告
课程名称：数据结构
报告题目：二叉树的基本操作 学生姓名：肖琳桂、康政、张小东、张帆 所在学院：信息科学与工程学院 专业班级：软工本1402
学生学号：144300211、02、14、08 指导教师：李春庭
2015年12月31日 课程设计任务书
报告题目 学生姓名 二叉树的基本操作 肖琳桂 专业康政 班级 软工本 指导教师 1402 李春庭 完成时间 2周 职称 讲师 总体设计要求和主要功能 设计一个程序，实现二叉树的创建以及二叉树的遍历（包括先序遍历、中序遍历、后序遍历和层次遍历），计算并输出二叉树的深度和结点个数，功能要求： 1．二叉树以二叉链表存储，结点数据类型采用字符表示，按二叉树的先序遍历序列创建。 2．用文本编辑器编写一个data.txt的文件,包含3个以上创建按二叉树的先序遍历序列(即序列中包含空树节点)，每个序列长度不少于10个，在运行程序时自动载入，也可以由键盘输入创建二叉树。| 3．菜单功能：创建二叉树（二级菜单说明 选择文件中的第几个，输出创建二叉树的深度及结点数，若失败则有相应提示），遍历序列（显示先序，中序，后序和层次遍历结果），结点的孩子信息，退出系统。 工作内容及时间进度安排 第17周： 周1---周2：立题、论证方案设计 周3---周5 ：程序设计及程序编码 第18周： 周1---周3 ：程序调试 周4---周5 ：验收答辩
摘 要
本课程设计主要说明如何在C++编程环境下实现二叉树的遍历，遍历方式包括:二叉树的先序遍历、中序遍历、后序遍历，层次遍历等四种遍历方式。同时，此次课程设计还包括了求二叉树深度和结点个数，结点的孩子信息，以及对文件的操作，用文件读取的方式实现对二叉树的建立。以通过此次课程设计，使学生充分掌握树的基本操作，以及对线性存储结构的理解。同时，在对树的遍历的操作过程中，同样是运用递归的方式实现遍历，在对树实现层次操作的时候，要求用循环队列的操作方式来实现层次遍历。此次课程设计对数据结构内容综合性的运用的要求较高。
关键词：二叉树，先序遍历，中序遍历，后序遍历，层次遍历，节点，线性存储, 节点的孩子信息
目 录
课程设计任务书...................................................... 1 一、需求分析........................................................ 4
1．问题描述 ..................................................... 4 2．功能要求 ..................................................... 4 二、概要设计........................................................ 5
1.总体设计图 .................................................... 5 2.数据结构设计 .................................................. 5 3.算法设计 ...................................................... 5 4.主要模块及模块之间的关系 ...................................... 5 三、详细设计........................................................ 6
1.结构体（或类）设计 ............................................ 6 2. 主要模块实现的流程图 ......................................... 6 3.算法设计 ...................................................... 7 四、测试运行........................................................ 8
1．登录和主界面运行效果图 ....................................... 8 2．运行说明 ..................................................... 8 3. 运行效果图 ................................................... 8 五、结论与心得..................................................... 10
1.总体评价 ..................................................... 10 2.所做的工作及体会 ............................................. 10 六、程序附录（源代码）............................................. 13 七、参考文献....................................................... 20
一、需求分析 1．问题描述
设计一个二叉树。二叉树形象地说即树中每个节点最多只有两个分支，它是一种重要的数据类型。可以运用于建立家谱，公司所有的员工的职位图，以及各种事物的分类和各种机构的职位图表等。二叉树是通过建立一个链式存储结构，达到能够实现前序遍历，中序遍历，后序遍历，层次遍历。以及能够从输入的数据中得知二叉树的叶子结点的个数，二叉树的深度。在此，二叉树的每一个结点中必须包括：值域，左指针域，右指针域。我们抽象出下列问题：实现文件操作，运用文件输入流，将已经写好二叉树序列的txt文本文件，加载到程序中，实现文件创建二叉树。然后采用链表存储的方式遍历二叉树（先序遍历、中序遍历、后序遍历、层次遍历）。层次遍历运用循环队列的方法实现，需要重新定义队头和队尾，以及队列的最大长度，并且在屏幕上实现输出显示。
2．功能要求
(1)用菜单的形式实现操作界面，提供（1—4）个功能选项，功能分别为创建二叉树、遍历序列、节点的孩子信息、退出系统。
(2)创建二叉树。要求用文件读取和键盘输入两种不同的方式实现二叉树的创建。二级菜单说明，输出创建二叉树的深度及结点数，若失败则有相应提示。
(3)遍历序列。显示先序，中序，后序和层次遍历结果。先序遍历、中序遍历、后序遍历用递归的方法实现遍历。层次遍历，用循环队列的方法实现。
(4)每次实现一项操作之后，要有相应的提示返回菜单。
4