二叉树基本操作演示程序设计与实现.doc

XXX大学 电子与信息工程学院 数据结构课程设计报告 ( 2012——2013年度第一学期) 课程名称： 数据结构课程设计 题 目 ：6.2二叉树的基本操作演示程序 院 系： 计算机科学系 班 级： 10软件本二班 姓 名： X X 学 号： 100913005 指导教师： 孙凌宇老师 成 绩： 2012 年 月 日  成 绩 评 定 一、 指导教师评语 二、 成绩 成绩 备注 指导教师： 日 期： 年 月 日  设计题目一：6.2二叉树基本操作演示程序的设计与实现 一、设计要求 1．问题描述 设计一个与二叉树基本操作相关的演示程序。 2．需求分析 （1）创建二叉树。按照用户需要的二叉树，构建二叉树。 （2）将创建的二叉树，以树状形式输出。 （3）分别以先序、中序、后序三种遍历访问二叉树。（4）输出二叉树的叶子结点及叶子结点的个数。 （5）输出二叉树的高度。 二、概要设计 为了实现以上功能，可以从3个方面着手设计。 主界面设计 为了实现二叉树的相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本程序。 本程序主控菜单运行界面如图1所示。 图1“二叉树基本操作程序”主菜单 2．存储结构设计 本程序采用二叉链式存储类型（BiTNode）存储二叉树的结点信息。二叉树的链表中的结点至少包含3个域：数据域（data）、左孩子指针域（Lchild）、和右孩子指针域（Rchild）。 3．系统功能设计 本程序除了完成二叉树的创建功能外还设置了8个子功能菜单。由于这8个子功能都是建立在二叉树的构造上的，所以二叉树的创建由主函数main（）实现。8个子功能的设计描述如下： (1) 树状输出二叉树。树状输出二叉树有函数TranslevePrint（）实现。当用户选择该功能时，系统即以树状的形式输出用户所创建的二叉树。 (2)先序遍历二叉树。由函数PreOrder（）实现。该功能按照先序遍历访问二叉树的方法输出先序遍历序列。 (3)中序遍历二叉树。由函数InOrder（）实现。该功能按照中序遍历访问二叉树的方法输出中序遍历序列。 (4)后序遍历二叉树。由函数PostOrder（）实现。该功能按照后序遍历访问二叉树的方法输出后序遍历序列。 (5)输出叶子结点。该功能采用先序遍历二叉树的方法，依次输出叶子结点。由函数PreOrderLeaf（）实现。 (6)输出叶子结点个数。该功能计算并输出二叉树中叶子结点的个数，由LeafCount（）函数实现。采用递归算法计算二叉树中叶子结点的个数，算法思想是：当二叉树为空树时，叶子结点总数为0；当二叉树只有一个结点时，叶子结点个数为1；否则，叶子结点个数等于左、右子树叶子结点数之和。 (7)输出二叉树的深度。该功能即输出二叉树结点所在层次的最大值。由函数PostTreeDepth（）实现，采用后序遍历的递归算法求二叉树的深度。 (8)退出。由exit（0）函数实现。 三、模块设计 1．模块设计 本程序包含三个模块：主程序模块、建立二叉树模块和工作区模块。其调用关系如图2所示。 主程序模块建立二叉树模块 主程序模块 建立二叉树模块 工作区选择模块 图2 模块调用示意图 2．系统子程序及功能设计 本系统共设置11个子程序，各子程序的函数名及功能说明如下： (1) void CreateBiTree(BiTree *bt) //建立二叉树 (2) void TranslevelPrint(BiTree bt) //树状打印二叉树 (3) void Visit(char ch) //输出结点 (4) void PreOrder(BiTree root) //先序遍历二叉树 (5) void InOrder(BiTree root) //中序遍历二叉树 (6) void PostOrder(BiTree root) //后序遍历二叉树 (7) void PrePrderLeaf(BiTree root) //输出叶子结点 (8) int LeafCount(BiTree root) //输出叶子结点的个数 (9) int PostTreeDepth(BiTree root) //输出二叉树的深度 (10) void mainwor