二叉树的基本操作

1、成绩中南大学信息科学与工程学院数据结构实 验报 告实验名称:二叉树基本操作班 级学号:姓 名:实验题目实现二叉树的基本操作的代码实现二实验目的1、掌握二叉树的基本特性2、掌握二叉树的先序、中序、后序的递归遍历算法3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实验要求认真阅读书上给出的算法编写程序并独立调试四、概要设计ADT Bin aryTree数据对象D： D是具有相同特性的数据元素的集合。数据关系R：/ 若 D=e，则 R=e，称 BinaryTree 为空二叉树；/若D#0，则R=H，H是如下二元关系；/ (1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；/

2、 (2)若 D-rootM，则存在 D-root=D1,Dr，且 DICDr =0；/ (3)若D1M0,则D1中存在惟一的元素x1, vroot,x1wH,且存在D1上的关系H1匸H；若DrM0，则Dr中存在惟一的元素xr，vroot,xrwH,且存在上的关系Hr CH； H=vroot,x1,vroot,xr,H1,Hr；/ (4) (D1,H1)是一棵符合本定义的二叉树，称为根的左子树；(Dr,Hr)是一棵符合本定 义的二叉树，称为根的右子树。基本操作：CreateBiTree( &T, defi ni tion )/初始条件：definition给出二叉树T的定义。/操作结果：按def

3、initon构造二叉树T。BiTreeDepth( T )/初始条件：二叉树T存在。/操作结果：返回T的深度。PreOrderTraverse( T, visit()/初始条件：二叉树T存在，Visit是对结点操作的应用函数。/操作结果：先序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。InO rderTraverse( T, visit()/初始条件：二叉树T存在，Visit是对结点操作的应用函数。/操作结果：中序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。PostOrderTraverse( T, vis

4、it()/初始条件：二叉树T存在，Visit是对结点操作的应用函数。/操作结果：后序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操 作失败。LeafNodes(p)/初始条件：二叉树T存在。/操作结果：返回T的叶子结点数。BothNodes(p)初始条件：二叉树T存在。/操作结果：返回T的度为2的结点数。五、详细设计1、给出本数据的存储结构定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW -22、实现二叉树的抽象数据类型如下：typed

5、ef intStatus;typedef char TElemType;定义二叉树的数据元素类型为chr3、存储实现的抽象数据类型如下:BiTNode0120data;BiTNode0120BiTNode0120data;BiTNode0120BiTNode0120*lchild; /左孩子指针*rchild;右孩子指针TElemTypestructstruct BiTNode0120, *BiTree;4、运算的函数声明：Status CreateBiTree0120 (BiTree T, defi ni tion )/构建二叉树Status PreOrder0120 (BiTree p)/

6、先 序遍历Status In Order0120 (BiTree p)/中 序遍历Status PostOrder0120 (BiTree p)/后 序遍历Status BTNodeDepth0120 (BiTree p)/求 二叉树的深度Status LeafNodes0120 (BiTree p,i nt *i)/求 二叉树叶子结点的个数 void getDataFromFile0120(char fileName,BiTree & root);Status BothNodes0120 (BiTree p,int *i)/求度为 2 的结点数5、给出操作实现的伪码Status create

7、BiTree0120 (BiTree &root,char in ,i nt beg in 1,i nt en d1,char post, int beg in 2,i nt en d2)根据给定的中序序列in,后序序列post，构造二叉树root其中：beg ini, en di分别为叉树的中序序列在in冲的开始位置(序号，数组下标 +1)、结束位置；其中：begin2, end2分别为叉树的后序序列在post冲的开始位置(序号，数组下 标+1 )、结束位置；char r;int i;int mi;中序序列中，左子树根位置int m2;后序序列中，左子树最后一个结点位置if(begi n1-

8、e nd1!=begi n2-e nd2) return ERROR;if(e nd1-begi n1=0)root=(BiTree)malloc(sizeof(BiTNode);r=poste nd2;root-data=r; /根for(i=beg in 1;iv=e nd1;i+)if(i ni=r) break;m1=i-1;m2=beg in 2+i-beg in1-1;root-lchild=NULL; root-rchild=NULL;if(createBiTreeO12O(root-lchild ,in,begin1,m1,post,begin2,m2)=ERROR) 构造左子

9、树printf(初始化二叉树出错！ nn请检查初始数据！ nn”)； if(createBiTreeO12O(root-rchild ,in,m1+2,end1,post,m2+1,end2-1)=ERR0R) 构造右子树printf(初始化二叉树出错！ nn请检查初始数据！ nn”)；elseroot=NULL;return OK;void getDataFromFile0120 (char fileName,BiTree &root) 从文件fileName中读取数据构造二叉树rootFILE *fp;char inO rder0120 100;char postOrder0120 100

10、;int a1,a2,b1,b2;fp=fope n( fileName,r);fsca nf(fp,%sn,i nO rder0120);fsca nf(fp,%sn,postOrder0120);fclose(fp);a1=strle n( i nOrder0120:);中序序列第一个字符位置a2=strle n(inO rder0120)-1;中序序列最后一个字符位置b1=strle n( postOrder0120:); 后序序列第一个字符位置 b2=strle n( postOrder0120)-1;后序序列最后一个字符位置if(createBiTree0120 (root,i nO

11、rder0120,a1,a2,postOrder0120,b1,b2)=ERROR) printf(初始化二叉树出错！ nn请检查初始数据！ nn”)；elseprintf(初始化二叉树成功！)；Status PreOrder0120 (BiTree p) / 先序遍历二叉树if ( p!= NULL ) pri ntf(%c, p-data);Pre0rder0120 ( p-lchild );Pre0rder0120 ( p-rchild);return OK;Status InOrder0120 (BiTree p) / 中序遍历二叉树if( p!= NULL ) In Order012

12、0 ( p-lchild );pri ntf(%c, p-data);In Order0120 ( p-rchild);return OK;Status PostOrder0120 (BiTree p) / 后序遍历二叉树 if ( p!= NULL ) PostOrder0120 ( p-lchild );PostOrder0120 ( p-rchild);pri ntf(%c, p-data);return OK;Status BTNodeDepth0120 (BiTree p)求二叉树的深度in t lchilddep,rchilddep;if(p=NULL)return 0;elsel

13、childdep=BTNodeDepth0120 (p-lchild); rchilddep=BTNodeDepth0120 (p-rchild);retur n(lchilddeprchilddep)?(lchilddep+1):(rchilddep+1); return OK;Status LeafNodes0120 (BiTree p,i nt *i)求二叉树的叶子结点 int j;if(p!=NULL)if(p-lchild!=NULL|p-rchild!=NULL)j = *i;j+;*i = j；LeafNodes0120 (p-lchild,i);LeafNodes0120(p-

14、rchild,i); return OK;Status BothNodes0120 (BiTree p,int *i)求度为 2 的结点数 int j;if(p!=NULL) if(p-lchild!=NULL&p-rchild!=NULL) j=*i;j+； *i = j;BothNodes0120 (p-lchild,i);BothNodes0120(p-rchild,i); return OK;七、程序的运行测试及结果测试用例1：构造二叉树测试用例2：先序遍历测试用例3：中序遍历 TOC o 1-5 h z 枕退岀:+:*1 构造二叉树*2.先序遍历*相中序遍历*羁后续遍历*槪.叶子结点数*梱.深度*郴度为2的结点数*：|=|=4=|=4=|=4=|=|=|=|=4=|=4=|=4=|=|=|=|=4=|=4=|=4=|=|=|