数据结构课程设计---二叉树的操作.doc

数据结构课程设计 题 目： 二叉树的操作 学生姓名： 学 号： 系部名称： 计算机科学与技术系 专业班级： 指导教师：  课 程 设 计 任 务 书 组内学生姓名 人数 1 系部名称 计算机科学与技术系 专业 软件工程 班级、学号 指导教师姓名 职称 从事专业 软件工程 题目名称 二叉树的操作 课程设计的目的、意义 目的在于通过课程设计的综合训练，帮助学生深入系统地掌握数据结构课程的主要内容和基本方法，培养学生综合运用所学知识分析解决实际问题和编程等实际动手能力。 熟练的掌握二叉树的基本操作。 二、课程设计的主要内容、技术要求（包括原始数据、技术参数、设计要求、工作量要求等） 实现二叉树的先序、中序和后序遍历；求二叉树的结点总数、叶子结点个数及二叉树的深度。 三、课程设计完成后应提交的成果 完整的论文和部分源代码 四、课程设计的工作进度安排 （1）复习与设计题目相关的数据结构知识，查阅文献资料 （1天） （2）确定设计方案，设计模块结构及各模块流程 （1天） （3）编码、调试与测试 （5天） （4）撰写课程设计报告 （2天） （5）设计演示 （1天） 五、主要参考资料 1.严蔚敏《数据结构》C语言版清华大学出版社 六、备注 指导教师签字： 年 月 日 教研室主任签字： 年 月 日  程序要求 1）完成二叉树的基本操作。 2）建立以二叉链表为存储结构的二叉树； 3）实现二叉树的先序、中序和后序遍历； 4）求二叉树的结点总数、叶子结点个数及二叉树的深度。 算法分析 建立以二叉链表为存储结构的二叉树，在次二叉树上进行操作； 1先序遍历二叉树的操作定义为： 若二叉树唯恐则为空操作；否则 （1）访问根节点； （2）先序遍历做字数和； （3）先序遍历有子树； 2中序遍历二叉树的操作定义为： 若二叉树为空，则空操作;否则 （1）中序遍历做子树； （2）访问根节点； （3）中序遍历有子树； 3后续遍历二叉树的操作定义为： 若二叉树为空则为空操作；否则 （1)后序遍历左子树 ; （2)后序遍历右子树; （3）访问根节点 ； 二叉树的结点总数、叶子结点个数及二叉树的深度。 二叉树的基本操作和 算法实现 二叉树是一种重要的非线性数据结构，是另一种树形结构，它的特点是每个节点之多有两棵子树(即二叉树中不存在度大于2的结点)，并且二叉树的结点有左右之分，其次序不能随便颠倒。 二叉树创建 二叉树的很多操作都是基于遍历实现的。二叉树的遍历是采用某种策略使得采用树形结构组织的若干年借点对应于一个线性序列。二叉树的遍历策略有四种：先序遍历 中续遍历 后续遍历和层次遍历。 基本要求 1 从键盘接受输入数据（先序），以二叉链表作为存储结构，建立二叉树。 2 输出二叉树。 3 对二叉树进行遍历（先序，中序，后序和层次遍历） 4 将二叉树的遍历打印出来。 一．问题描述 二叉树的很多操作都是基于遍历实现的。二叉树的遍历是采用某种策略使得采用树型结构组织的若干结点对应于一个线性序列。二叉树的遍历策略有四种：先序遍历、中序遍历、后序遍历和层次遍历。 二．基本要求 1．从键盘接受输入数据（先序），以二叉链表作为存储结构，建立二叉树。 2．输出二叉树。 3．对二叉树进行遍历（先序、中序、后序和层次遍历）。 4．将二叉树的遍历结果打印输出。 三．提示与分析 1．主要数据类型 ① 二叉链表 # define DataType char /*元素类型*/ typedef struct BiTNode {DataType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; ② 二叉树的遍历序列 DataType preorder[n]; DataType inorder[n]; DataType postorder[n]; 2．基本功能分析 ① 采用教材上类似于