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

二叉树基本操作演示程序的设计与实现 2012级电器信息类 注意：文档以word格式提供，文件名起名规则：学号+姓名+实验报告名称 首先请输入二叉树结点序列： 请按菜单提示操作： ----------------------------欢迎使用二叉树基本操作程序------------------------------- 菜单选择 1. 树状输出二叉树 2. 先序遍历二叉树 3. 中序遍历二叉树 4. 后序遍历二叉树 5. 输出叶子结点 6. 输出叶子结点个数 7. 输出二叉树的深度 8. 括号形式输出二叉树 9. 退出 -------------------------------------------------------------------------------------------------- 图1 二叉树基本操作程序主菜单 2、存储结构设计 本程序采用二叉链式存储类型(BiTNode)存储二叉树的结点信息。二叉树的链表中的结点至少包含3个域：数据域(data)、左孩子指针域(lchild)、右孩子指针域(rchild)。 3、系统功能设计 本程序除了完成二叉树的创建功能外还设置了9个子功能菜单。由于这9个子功能都是建立在二叉树的构造上的，所以二叉树的创建由主函数main()实现。9个子功能的设计描述如下： ⑴树状输出二叉树。树状输出二叉树由函数TranslevelPrint()实现。当用户选择此功能时，系统即以树状的形式输出用户所创建的二叉树。 ⑵先序遍历二叉树。由函数Preorder()实现。该功能按照先序遍历访问二叉树的方法输出先序序列。 ⑶中序遍历二叉树。由函数Inorder()实现。该功能按照中序遍历访问二叉树的方法输出中序序列。 ⑷后序遍历二叉树。由函数Postorder()实现。该功能按照后序遍历访问二叉树的方法输出后序序列。 ⑸输出叶子结点。该功能采用先序遍历二叉树的方法依次输出叶子结点。由函数Preorderleaf()实现。 ⑹输出叶子结点个数。该功能计算并输出二叉树中叶子结点的个数，由LeafCount()实现。采用递归算法计算二叉树中叶子结点的个数，算法思想是：当二叉树为空树时，叶子结点总数为0；当二叉树只有1个结点时，叶子结点总数为1；否则，叶子结点个数等于左右子树叶子结点数之和。 ⑺输出二叉树的深度。该功能输出二叉树的深度，由函数PostorderDepth()实现，采用后序遍历的递归算法求二叉树的深度。 ⑻括号形式输出二叉树。以括号形式输出二叉树由函数，由函数output()实现。当用户选择此功能时，系统即以括号形式输出二叉树。 ⑼退出。由exit(0)函数实现。 三、模块设计 1、模块设计 本程序包含三个模块，主程序模块、建立二叉树模块和工作区选择模块。其调用关系如图2所示。 图2 模块调用示意图 2、系统子程序用功能设计 本系统共设置12个子程序，各子程序的函数名及功能说明如下： ⑴void CreateBiTree(BiTree T) //先序建立二叉树 ⑵void TranslevelPrint(BiTree T) //树形打印二叉树 ⑶void Visit(char ch) //输出结点 ⑷void Preorder(BiTree T) //先序遍历二叉树 ⑸void Inorder(BiTree T) //中序遍历二叉树 ⑹void Postorder(BiTree T) //后序遍历二叉树 ⑺void PreorderLeaf(BiTree T) //输出叶子结点 ⑻int LeafCount(BiTree T) //输出叶子结点的个数 ⑼int PostorderDepth(BiTree T) //输出二叉树的深度 ⑽void output(BiTree T) //以括号形式输出二叉树 ⑾void mainwork() //主工作函数，操作区用户界面 ⑿void main() //主函数。创建二叉树，调用工作区模块函数 3、函数主要调用关系图 本系统12个子程序之间的主要调用关系如图3所示。图中数字是各函数的编号。 图3系统函数调用