二叉树仿真指针储存结构操作设计说明书.doc

数学与计算机学院 课程设计说明书 课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 题 目:二叉树的仿真指针储存结构操作 年级/专业/班: 学 生 姓 名: 学　　 号: 开 始 时 间: 2011 年 12 月 08 日 完 成 时 间: 2011 年 12 月 20 日 课程设计成绩： 学习态度及平时成绩（30） 技术水平与实际能力（20） 创新（5） 说明书（计算书、图纸、分析报告）撰写质量（45） 总 分（100） 指导教师签名： 年 月 日 目 录 引 言 - 1 - 1 需求分析 - 1 - 1.1任务与分析 - 1 - 1.2测试数据 - 2 - 1.2.1二叉树1 - 2 - 1.2.2二叉树2 - 3 - 1.2.3二叉树3 - 3 - 2 概要设计 - 4 - 2.1 ADT描述 - 4 - 2.2 程序模块结构 - 5 - 2.3 各功能模块 - 5 - 3　详细设计 - 6 - 3.1结构体定义 - 6 - 3.2 栈模板定义 - 6 - 3.3 类定义 - 7 - 3.4 初始化 - 8 - 3.5 创建二叉树操作 - 9 - 3.6 输出二叉树操作 - 9 - 3.7 先序遍历操作 - 10 - 3.8 中序遍历操作 - 11 - 3.9 后序遍历操作 - 13 - 3.10 撤销二叉树操作 - 15 - 3.11 查找操作 - 15 - 3.12 求各节点度操作 - 16 - 3.13 求二叉树深度操作 - 16 - 3.14 判断操作 - 17 - 3.15 菜单函数 - 19 - 4 调试分析 - 21 - 4.1问题分析 - 21 - 4.2时间复杂度分析 - 21 - 4.3经验和体会 - 22 - 5　用户使用说明 - 22 - 6　测试结果 - 23 - 6.1菜单函数 - 23 - 6.2创建二叉树函数 - 23 - 6.3输出二叉树函数 - 24 - 6.4先序遍历二叉树 - 25 - 6.5中序遍历二叉树 - 26 - 6.6后序遍历二叉树 - 26 - 6.7撤销二叉树函数 - 27 - 6.8查找函数 - 27 - 6.8.1基于二叉树1的查找成功 - 27 - 6.8.2基于二叉树1查找失败 - 28 - 6.9求各节点度函数 - 28 - 6.10求二叉树深度函数 - 29 - 6.11判断函数 - 29 - 结 论 - 31 - 致 谢 - 32 - 参考文献 - 33 - 摘 要 随着计算机的应用以惊人的速度普及，计算机的应用早已不局限于科学计算，而更多的应用在现实生活中。数据的储存结构多种多样，其中树型结构是以分支关系定义的层次结构，是一种重要的非线性结构。树型结构在客观世界中广泛存在，例如在计算机文件管理和信息组织方面用树型结构来表示，又如人类的家庭族谱以及各种社会组织机构也都可以用树型结构来表示。而二叉树是一种有着重要用途的树型结构。研究二叉树的基本概念、储存结构以及相关运算，对研究一般树的储存和运算有着重要意义。本文研究二叉树的仿真指针储存结构的实现以及一般操作。 关键词：储存结构；二叉树；仿真指针储存；一般操作。引 言 数据结构就是反映数据在内存中的存储方式以及对数据进行的一系列操作。数据结构可以和生活实际相联系，用于解决生活中实际问题。课程设计正是基于这个目的，通过课程设计，锻炼我们发现问题，解决问题的能力。该次课程设计任务是实现有向图的邻接矩阵存储方式及其相关操作，采用VS2010编程环境。 1 需求分析 1.1任务与分析 二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。如右图所示，二叉树按仿真指针存储为： 数组下标 data lchild rchild 0 A 1 2 1 B 3 4 2 C 5 6 3 D -1 -1 4 E -1 -1 5 F -1 -1 6 G -1 -1 编写程序实现二叉树仿真指针存储结构，并实现如下操作： 输出该二叉树； 写出三种遍历算法，输出遍历序列； 二叉树的撤销操作 查找数据元素操作 求各结点度的操作 求出该二叉树的深度 判断该二叉树是否是完全二叉树？ 数组下标 data lchild rchild 数组下标 data lchild rchild 数组下标 data lchild rchild