数据结构第三次实验数据构第三次实验.doc

实验四 树的操作与应用 【实验目的】 1．熟练掌握二叉树的二叉链表存储结构 2．掌握二叉树的非线性和递归性特点 3．熟练掌握二叉树的递归遍历操作的实现方法，掌握二叉树的非递归遍历操作的实现 4．加深对二叉树结构和性质的理解，逐步培养解决实际问题的编程能力 【实验内容】 1．定义二叉树的链式存储结构； 2．实现二叉树的基本操作：建空树、销毁二叉树、生成二叉树(先序,中序或后序)、判二叉树是否为空、 3．求二叉树的深度、求二叉树的根等基本算法； 4．实现二叉树的递归(先序、中序或后序)遍历算法； 【实验指导】 1．首先将二叉树的链式存储结构定义放在一个头文件：如取名为BinTreeDef.h。 2．将二叉树的基本操作算法也集中放在一个文件之中，如取名为BinTreeAlgo.h。包含关于二叉树的链式结构操作的一些基本算法，如：InitBiTree、DestroyBiTree、CreateBiTree、BiTreeEmpty、BiTreeDepth、Root、PreOrderTraverse、InOrderTraverse 等。 3．将函数的测试和主函数组合成一个文件，如取名为BinTreeUse.cpp。 利用二叉树的链式存储结构，设计一组输入数据（假定为一组整数或一组字符），能够对二叉树进行如下操作： 1．创建一棵空二叉树； 2．对一棵存在的二叉树进行销毁； 3．根据输入某种遍历次序输入二叉树中结点的值，依序建立二叉树； 4．判断某棵二叉树是否为空； 5．求二叉树的深度； 6．求二叉树的根结点，若为空二叉树，则返回一特殊值； 7．二叉树的遍历，即按某种方式访问二叉树中的所有结点，并使每个结点恰好被访问一次； 8．编写主程序，实现对各不同的算法调用； 实现要求如下： “构造空二叉树算法”操作结果：构造一个空二叉树T； “销毁二叉树算法”初始条件: 二叉树T 存在；操作结果: 销毁二叉树T ； “创建二叉树算法”初始条件:可以根据先序、中序和后序输入二叉树中结点的值（可为字符型或整型）；操作结果: 以选择的某种次序建立二叉树T ； “判二叉树是否为空算法”初始条件: 二叉树T 存在；操作结果: 若T 为空二叉树,则返回TRUE,否则FALSE ； “求二叉树的深度算法” 初始条件: 二叉树T 存在；操作结果: 返回T 的深度； “求二叉树的根算法??初始条件: 二叉树T 存在；操作结果: 返回T 的根； “先序递归遍历算法”初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数； 操作结果: 先序递归遍历T,对每个结点调用函数Visit 一次且仅一次； “中序递归遍历算法”初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数； 操作结果: 中序递归遍历T,对每个结点调用函数Visit 一次且仅一次； “后序递归遍历算法”初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数； 操作结果: 后序递归遍历T,对每个结点调用函数Visit 一次且仅一次； 长春大学计算机科学技术学院实验报告 日期_______________ 地点______________ 指导教师_____________ 成绩 实验四 树的操作与应用 利用二叉树的链式存储结构，设计一组输入数据（假定为一组整数或一组字符），能够对二叉树进行如下操作： 1．创建一棵空二叉树； 2．对一棵存在的二叉树进行销毁； 3．根据输入某种遍历次序输入二叉树中结点的值，依序建立二叉树； 4．判断某棵二叉树是否为空； 5．求二叉树的深度； 6．求二叉树的根结点，若为空二叉树，则返回一特殊值； 7．二叉树的遍历，即按某种方式访问二叉树中的所有结点，并使每个结点恰好被访问一次； 实现过程： 1、文件pubuse.h，与实验一相同； 2．文件BinTreeDef.h 中实现了二叉树的链式存储结构定义 typedef struct BiTNode { TElemType data； struct BiTNode *lchild,*rchild； /* 左右孩子指针*/ }BiTNode,*BiTree； 3． 文件BinTreeAlgo.h 中实现二叉树的基本操作（存储结构由BinTreeDef.h 定义） Status InitBiTree(BiTree T) { /* 操作结果: 构造空二叉树T */ T=NULL； return OK； } void DestroyBiTree(BiTree T) { /* 初始条件: 二叉树T 存在。操作结果: 销毁二叉树T */ if(T) /* 非空树*/ { if(T-lchild) /* 有左孩子*/ DestroyBiTree(T-lchild)； /* 销毁左孩子子树*/ if(T