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

《二叉树基本操作演示程序的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计报告XXX大学电子与信息工程学院数据结构课程设计报告(2012——2013年度第一学期)课程名称：数据结构课程设计题目：6.2二叉树的基本操作演示程序院系：计算机科学系班级：10软件本二班姓名：XX学号：100913005指导教师：孙凌宇老师成绩：2012年月日22数据结构课程设计报告成绩评定一、指导教师评语二、成绩成绩备注指导教师：日期：年月日22数据结构课程设计报告设计题目<一>：6.2二叉树基本操作演示程序的设计与实现一、设计要求1．问题描述设计一个与二叉树基本操作相关的演示程序。2．需求分析（1）创建二叉树。按照用户需要的二叉树，构建二叉树。（2）将创建的二叉树，以

2、树状形式输出。（3）分别以先序、中序、后序三种遍历访问二叉树。（4）输出二叉树的叶子结点及叶子结点的个数。（5）输出二叉树的高度。二、概要设计为了实现以上功能，可以从3个方面着手设计。1．主界面设计为了实现二叉树的相关操作功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本程序。本程序主控菜单运行界面如图1所示。图1“二叉树基本操作程序”主菜单22数据结构课程设计报告2．存储结构设计本程序采用二叉链式存储类型（BiTNode）存储二叉树的结点信息。二叉树的链表中的结点至少包含3个域：数据域（data）、左孩子指针域（Lchild）、和右孩子指针域（Rch

3、ild）。3．系统功能设计本程序除了完成二叉树的创建功能外还设置了8个子功能菜单。由于这8个子功能都是建立在二叉树的构造上的，所以二叉树的创建由主函数main（）实现。8个子功能的设计描述如下：(1)树状输出二叉树。树状输出二叉树有函数TranslevePrint（）实现。当用户选择该功能时，系统即以树状的形式输出用户所创建的二叉树。(2)先序遍历二叉树。由函数PreOrder（）实现。该功能按照先序遍历访问二叉树的方法输出先序遍历序列。(3)中序遍历二叉树。由函数InOrder（）实现。该功能按照中序遍历访问二叉树的方法输出中序遍历序列。(4)后序遍历二叉树。由函数PostOrder（）

4、实现。该功能按照后序遍历访问二叉树的方法输出后序遍历序列。(5)输出叶子结点。该功能采用先序遍历二叉树的方法，依次输出叶子结点。由函数PreOrderLeaf（）实现。(6)输出叶子结点个数。该功能计算并输出二叉树中叶子结点的个数，由LeafCount（）函数实现。采用递归算法计算二叉树中叶子结点的个数，算法思想是：当二叉树为空树时，叶子结点总数为0；当二叉树只有一个结点时，叶子结点个数为1；否则，叶子结点个数等于左、右子树叶子结点数之和。(7)输出二叉树的深度。该功能即输出二叉树结点所在层次的最大值。由函数PostTreeDepth（）实现，采用后序遍历的递归算法求二叉树的深度。(8)退

5、出。由exit（0）函数实现。三、模块设计1．模块设计22数据结构课程设计报告本程序包含三个模块：主程序模块、建立二叉树模块和工作区模块。其调用关系如图2所示。主程序模块建立二叉树模块工作区选择模块图2模块调用示意图2．系统子程序及功能设计本系统共设置11个子程序，各子程序的函数名及功能说明如下：(1)voidCreateBiTree(BiTree*bt)//建立二叉树(2)voidTranslevelPrint(BiTreebt)//树状打印二叉树(3)voidVisit(charch)//输出结点(4)voidPreOrder(BiTreeroot)//先序遍历二叉树(5)voidIn

6、Order(BiTreeroot)//中序遍历二叉树(6)voidPostOrder(BiTreeroot)//后序遍历二叉树(7)voidPrePrderLeaf(BiTreeroot)//输出叶子结点(8)intLeafCount(BiTreeroot)//输出叶子结点的个数(9)intPostTreeDepth(BiTreeroot)//输出二叉树的深度(10)voidmainwork()//主要工作函数。操作区用户界面(11)voidmain()//主函数。创建二叉树。调用工作区模块函数3．函数主要调用关系图本系统11个子程序之间的主要调用关系如图3所示。图中数字是各函数的编号。2

7、2数据结构课程设计报告10mainwork()98765423111main()图3系统函数调用关系图四、详细设计1．数据类型定义TypedefstructBiTNode//定义二叉树结点结构｛chardata;//数据域structBiTNode*LChild,*RChild;//左右孩子指针域｝2．系统主要子程序详细设计(1)主函数模块设计主函数，创建二叉树，调用工作区模块函数voidmain(){printf("