数据结构实验五 二叉树的定义及基本操作
1、实验目的
∙ 熟练掌握二叉树的二叉链表存储结构
∙ 掌握二叉树的非线性和递归性特点
∙ 熟练掌握二叉树的递归遍历操作的实现方法，掌握二叉树的非递归遍历操作的实现
∙ 掌握线索二叉树的定义和基本操作
∙ 加深对二叉树结构和性质的理解，逐步培养解决实际问题的编程能力
2、实验内容：
∙ 定义二叉树的链式存储结构；
∙ 实现二叉树的基本操作：建空树、销毁二叉树、生成二叉树(先序,中序或后序)、判二叉树是否为空、
∙ 求二叉树的深度、求二叉树的根等基本算法；
∙ 实现二叉树的递归(先序、中序或后序)遍历算法；
1．问题描述：
利用二叉树的链式存储结构，设计一组输入数据（假定为一组整数或一组字符），能够对二叉树进行如下操作：
1) 创建一棵空二叉树；
2) 对一棵存在的二叉树进行销毁；
3) 根据输入某种遍历次序输入二叉树中结点的值，依序建立二叉树；
4) 判断某棵二叉树是否为空；
5) 求二叉树的深度；
6) 求二叉树的根结点，若为空二叉树，则返回一特殊值；
7) 二叉树的遍历，即按某种方式访问二叉树中的所有结点，并使每个结点恰好被访问一次；
编写主程序，实现对各不同的算法调用；
2．实现要求：
1) “构造空二叉树算法”操作结果：构造一个空二叉树T；
2) “销毁二叉树算法”初始条件: 二叉树T 存在； 操作结果: 销毁二叉树T ；
3) “创建二叉树算法”初始条件:可以根据先序、中序和后序输入二叉树中结点的值（可为字符型或整型）；操作结果: 以选择的某种次序建立二叉树T ；
4) “判二叉树是否为空算法”初始条件: 二叉树T 存在；操作结果: 若T 为空二叉树,则返回TRUE,否则FALSE ；
5) “求二叉树的深度算法” 初始条件: 二叉树T 存在；操作结果: 返回T 的深度；
6) “求二叉树的根算法”初始条件: 二叉树T 存在；操作结果: 返回T 的根；
7) “先序递归遍历算法”初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数；操作结果: 先序递归遍历T,对每个结点调用函数Visit 一次且仅一次；
8) “中序递归遍历算法”初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数；操作结果: 中序递归遍历T,对每个结点调用函数Visit 一次且仅一次；
9) “后序递归遍历算法”初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数；操作结果: 后序递归遍历T,对每个结点调用函数Visit 一次且仅一次；
3、实验指导
1．首先将二叉树的链式存储结构定义放在一个头文件：如取名为BinTreeDef.h。
2．将二叉树的基本操作算法也集中放在一个文件之中，如取名为BinTreeAlgo.h。包含关于二叉树的链式
结构操作的一些基本算法，如：InitBiTree、DestroyBiTree、CreateBiTree、BiTreeEmpty、BiTreeDepth、Root、PreOrderTraverse、InOrderTraverse 等。
3．将函数的测试和主函数组合成一个文件，如取名为BinTreeUse.cpp。
4、基本实验的参考程序
（一） 基本实验的参考程序
1、文件pubuse.h，与实验一相同；
2．文件BinTreeDef.h 中实现了二叉树的链式存储结构定义
typedef struct BiTNode
{
TElemType data；
struct BiTNode *lchild,*rchild； /* 左右孩子指针*/
}BiTNode,*BiTree；
3． 文件BinTreeAlgo.h 中实现二叉树的基本操作（存储结构由BinTreeDef.h 定义）
/* 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->rchild) /* 有右孩子*/
DestroyBiTree(T->rchild)； /* 销毁右孩子子树*/
free(T)； /* 释放根结点*/
T=NULL； /* 空指针赋0 */
}
}
#define ClearBiTree DestroyBiTree
void CreateBiTree(BiTree &T)
{ /* 算法6.4:按先序次序输入二叉树中结点的值（可为字符型或整型，在主程中*/
/* 定义），构造二叉链表表示的二叉树T。变量Nil 表示空（子）树。有改动*/
TElemType ch；
#ifdef CHAR
scanf("%c",&ch)；
#endif
#ifdef INT
scanf("%d",&ch)；
#endif
if(ch==Nil) /* 空*/
T=NULL；
else
{
T=(BiTree)malloc(sizeof(BiTNode))；
if(!T)
exit(OVERFLOW)；
T->data=ch； /* 生成根结点*/
CreateBiTree(T->lchild)； /* 构造左子树*/
CreateBiTree(T->rchild)； /* 构造右子树*/
}
}
先序中序后序遍历二叉树
Status BiTreeEmpty(BiTree T)
{ /* 初始条件: 二叉树T 存在*/
/* 操作结果: 若T 为空二叉树,则返回TRUE,否则FALSE */
if(T)
return FALSE；
else
return TRUE；
}
int BiTreeDepth(BiTree T)
{ /* 初始条件: 二叉树T 存在。操作结果: 返回T 的深度*/
int i,j；
if(!T)
return 0；
if(T->lchild)
i=BiTreeDepth(T->lchild)；
else
i=0；
if(T->rchild)
j=BiTreeDepth(T->rchild)；
else
j=0；
return i>j?i+1:j+1；
}
TElemType Root(BiTree T)
{ /* 初始条件: 二叉树T 存在。操作结果: 返回T 的根*/
if(BiTreeEmpty(T))
return Nil；
else
return T->data；
}
TElemType Value(BiTree p)
{ /* 初始条件: 二叉树T 存在，p 指向T 中某个结点*/
/* 操作结果: 返回p 所指结点的值*/
return p->data；
}
void Assign(BiTree p,TElemType value)
{ /* 给p 所指结点赋值为value */
p->data=value；
}
void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数。算法6.1，有改动*/
/* 操作结果: 先序递归遍历T,对每个结点调用函数Visit 一次且仅一次*/
if(T) /* T 不空*/
{
Visit(T->data)； /* 先访问根结点*/
PreOrderTraverse(T->lchild,Visit)； /* 再先序遍历左子树*/
PreOrderTraverse(T->rchild,Visit)； /* 最后先序遍历右子树*/
}
}
void InOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数*/
/* 操作结果: 中序递归遍历T,对每个结点调用函数Visit 一次且仅一次*/
if(T)
{
InOrderTraverse(T->lchild,Visit)； /* 先中序遍历左子树*/
Visit(T->data)； /* 再访问根结点*/
InOrderTraverse(T->rchild,Visit)； /* 最后中序遍历右子树*/
}
}
void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))
{ /* 初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数*/
/* 操作结果: 后序递归遍历T,对每个结点调用函数Visit 一次且仅一次*/
if(T) /* T 不空*/
{
PostOrderTraverse(T->lchild,Visit)； /* 先后序遍历左子树*/
PostOrderTraverse(T->rchild,Visit)； /* 再后序遍历右子树*/
Visit(T->data)； /* 最后访问根结点*/
}
}
4．在文件BinTreeUse.cpp 中，测试二叉树基本算法的调用
/* BinTreeUse.cpp 检验BinTreeAlgo.h 的主程序,利用条件编译选择数据类型(另一种方法) */
/* 二叉树的数据类型可以以是字符型，也可以是整型，可在程序中使用条件编译作出判断和控制*/
#define CHAR /* 字符型， 本例是采用字符型作为数据类型*/
/* #define INT /* 整型（二者选一） */
#include"pubuse.h" /* 与实验一的意义相同*/
#ifdef CHAR
typedef char TElemType；
TElemType Nil=' '； /* 字符型以空格符为空*/
#endif
#ifdef INT
typedef int TElemType；
TElemType Nil=0； /* 整型以0 为空*/
#endif
#include"BinTreeDef.h" /* 二叉树链式存储结构定义*/
#include"BinTreeAlgo.h" /* 二叉树基本算法和扩展算法定义*/

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。