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

＞弄」、4数学与计算机学院课程设计说明书课程名 称: 数据结构与算法课程设计课程代码：题 目：二叉树的仿真指针储存结构操作年级/专业/班：学生姓名：学 号: 开始时间：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创建二叉树操作 -8 -3.6输出二叉树操作 -9 -3.7先序遍历操作 -10 -3.8中序遍历操作 -11-3.9后序遍历操作 -12 -3.10撤销二叉树操作 -14 -3.11查找操作 -14 -3.12求各节点度操作 -15 -3.13求二叉树深度操作 -16 -3.14判断操作 -17 -3.15菜单函数 -18 -4调试分析 -20 -4.1问题分析 -20 -4.2时间复杂度分析 -20 -4.3经验和体会 -21 -5 用户使用说明 -21 -6 测试结果 -22 -6.1菜单函数 -22 -6.2创建二叉树函数 -22 -6.3 输出二叉树函数 -23 -6.4先序遍历二叉树 -24 -6.5中序遍历二叉树 -25 -6.6 后序遍历二叉树 -25 -6.7撤销二叉树函数 -26 -6.8查找函数 -26 -6.8.1基于二叉树1的查找成功 -26 -6.8.2基于二叉树1查找失败 -27 -6.9求各节点度函数 -27 -6.10求二叉树深度函数 -27 -6.11判断函数 -28 -结论 -29 -致谢 -30 -参考文献 -31 -摘要随着计算机的应用以惊人的速度普及，计算机的应用早已不局限于科学 计算，而更多的应用在现实生活中。

数据的储存结构多种多样，其中树型结构 是以分支关系定义的层次结构，是一种重要的非线性结构树型结构在客观世 界中广泛存在，例如在计算机文件管理和信息组织方面用树型结构来表示，又 如人类的家庭族谱以及各种社会组织机构也都可以用树型结构来表示而二叉 树是一种有着重要用途的树型结构研究二叉树的基本概念、储存结构以及相 关运算，对研究一般树的储存和运算有着重要意义本文研究二叉树的仿真指 针储存结构的实现以及一般操作关键词：储存结构；二叉树；仿真指针储存；一般操作数据结构就是反映数据在内存中的存储方式以及对数据进行的一系列操作数据结构 可以和生活实际相联系，用于解决生活中实际问题课程设计正是基于这个目的，通过课 程设计，锻炼我们发现问题，解决问题的能力该次课程设计任务是实现有向图的邻接矩 阵存储方式及其相关操作，采用VS2010编程环境1需求分析1.1任务与分析二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系如右图所示，二叉树按仿真指针存储为:数组下标da talchildrchild0A121B342C563D-1-14E-1-15F-1-16G-1-1B编写程序实现二叉树仿真指针存储结构，并实现如下操作:1） 输出该二叉树；2） 写出三种遍历算法，输出遍历序列；3） 二叉树的撤销操作4） 查找数据元素操作5） 求各结点度的操作6） 求出该二叉树的深度7） 判断该二叉树是否是完全二叉树?1.2测试数据1.2.1 二叉树 1数组下标da talchildrchild0A121B342C5-13D-1-14E-1-15F-1-11.2.2 二叉树 2数组下标da talchildrchild0A121B342C5-13D-1-14E6-15F-1-16G-1-11.2.3 二叉树 3数组下标da talchildrchild0A-1-12概要设计2.1 ADT描述ADT BinaryTree{数据对象:D=｛具有相同特性的数据元素的有限集合；｝数据关系:R=｛顺序储存｝基本操作:初始化一棵空树；建立一颗二叉树；输出一颗二叉树；二叉树的先序遍历；二叉树的中序遍历；二叉树的后序遍历；二叉树中数据元素的查找；求二叉树深度；求二叉树各结点度；判断二叉树是否是完全二叉树；销毁二叉树；等等；}ADT BinaryTree；2.2程序模块结构c1 ass Bi Tree一 1ength : int一 *BT : NodeTypestruct NodeTypetemp 1ate class SqStack+ ~BiTree 0一 data:E1emTypetypedef str i ng E1emType:-*stackspace : Type+ Menu 0void-LChiId : i nt—maxsize : int+ Creat 0void-RChiId : int—top : i nt+ Display 0vo i d+ SqStack (int m=30)+ PreOrder 0void+ 1sEmpty 0 : i nt+ 1nOrder 0void+ IsFul1 0 : int+ PostOrder 0vo i d+ Push (Type p) : void+ Destroy 0vo i d+ Pop 0 : Type+ Search 0voidconst int MaxSize二bU;+ GetTop 0 : Type+ PreDegree 0vo i d+ PreDepth (NodeType bt)i nt+ PreDepth_BT 0vo i d+ max (int x, int y)i nt+ IsFul1 BT 0void+ 1s Fu11 (NodeType m) 0bool2.3各功能模块BiTreeO;~BiTree() {};void Menu();void Crea t();void Display。

void PreOrder();void InOrder();void Pos tO rder();void Des troy ()void Searchvoid PreDegree();int PreDepth(NodeType bt);void PreDep th_BT();int max(i nt x,i nt y);void IsFull_BT();bool Is_Full(NodeType m);//构造函数//析构函数//菜单函数//建立二叉树//输出二叉树//先序遍历//中序遍历//后序遍历//撤销二叉树//查找数据元素//求各结点度//求二叉树的深度//调用 PreDep th(NodeType bt)//比较函数//调用Is_Full(NodeType m)//7)判断二叉树是否是完全二叉树3详细设计3.1结构体定义struet NodeType{ElemType data; //存放结点值int LCh il d,RChild; //存放左、右孩子的数组元素的下标 }；3.2栈模板定义#include "stdafx.h"template class SqStack{private:Type *stackspace;int maxsize;int top;public:SqS tack(i nt m=30);int IsEmp ty() { return to p==-1; }int IsFull() { return top二二maxsize-1; }void Push(Type p);Type Pop();Type Get Top();};template SqStack ::SqStack(int m){top=-1; maxsize=m; stackspace =new Type[maxsize];template{if(!IsFull()){ top++; stackspace[top]=p; }}template Type SqStack {Type p;if(!IsEmp ty()){ p=stackspace[top]; top--; } return p;}template Type SqStack {if(!IsEmp ty()) return st ackspace[ to p];}:Push(Type p):Pop():Ge tTop()3.3类定义class BiTree{private:int length;NodeType *BT; public:BiTree();~BiTree() {};voidMenu();voidCrea t();//建立二叉树voidDisplay();//1）输出二叉树voidPreOrder();//2）先序遍历voidInOrder();//2）中序遍历。