二叉树的基本操作实验报告

学号姓名实验日期2012-12-26实验室计算机软件技术实验指导教师设备编号401实验内容二叉树的基本操作一实验题目实现二叉树的基本操作的代码实现二实验目的1、掌握二叉树的基本特性2、掌握二叉树的先序、中序、后序的递归遍历算法3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实习要求（1）认真阅读书上给出的算法（2）编写程序并独立调试四、给出二叉树的抽象数据类型ADTBinaryTree{//数据对象D：D是具有相同特性的数据元素的集合。

//数据关系R：

//若D=Φ，则R=Φ，称BinaryTree为空二叉树；

//若D≠Φ，则R={H}，H是如下二元关系；

//（1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；

//（2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr=Φ；

//（3）若D1≠Φ，则D1中存在惟一的元素x1，<root,x1>∈H，且存在D1上的关系H1⊆H；若Dr≠Φ，则Dr中存在惟一的元素xr，<root,xr>∈H，且存在上的关系Hr⊆H；H={<root,x1>,<root,xr>,H1,Hr}；

//（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。//基本操作：

CreateBiTree(&T,definition)

//初始条件：definition给出二叉树T的定义。

//操作结果：按definiton构造二叉树T。BiTreeDepth(T)

//初始条件：二叉树T存在。

//操作结果：返回T的深度。PreOrderTraverse(T,visit())

//初始条件：二叉树T存在，Visit是对结点操作的应用函数。

//操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。InOrderTraverse(T,visit())

//初始条件：二叉树T存在，Visit是对结点操作的应用函数。

//操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。PostOrderTraverse(T,visit())

//初始条件：二叉树T存在，Visit是对结点操作的应用函数。

//操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。LeafNodes(p)

//初始条件：二叉树T存在。

//操作结果：返回T的叶子结点数。BothNodes(p)

//初始条件：二叉树T存在。//操作结果：返回T的度为2的结点数。五、详细设计1、给出本数据的存储结构定义#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineNULL0#defineOVERFLOW-22、实现二叉树的抽象数据类型如下:typedef int Status;typedef char TElemType;定义二叉树的数据元素类型为chr3、存储实现的抽象数据类型如下：typedef struct BiTNode0120{ TElemType data; struct BiTNode0120 *lchild;//左孩子指针 struct BiTNode0120 *rchild;//右孩子指针}BiTNode0120,*BiTree;4、运算的函数声明：StatusCreateBiTree0120(BiTreeT,definition)//构建二叉树StatusPreOrder0120(BiTreep)//先序遍历StatusInOrder0120(BiTreep)//中序遍历StatusPostOrder0120(BiTreep)//后序遍历StatusBTNodeDepth0120(BiTreep)//求二叉树的深度StatusLeafNodes0120(BiTreep,int*i)//求二叉树叶子结点的个数voidgetDataFromFile0120(charfileName[],BiTree&root);StatusBothNodes0120(BiTreep,int*i)//求度为2的结点数5、给出操作实现的伪码StatuscreateBiTree0120(BiTree&root,charin[],intbegin1,intend1,charpost[],intbegin2,intend2){//根据给定的中序序列in,后序序列post,构造二叉树root //其中：begin1，end1分别为叉树的中序序列在in[]中的开始位置（序号，数组下标+1）、结束位置；//其中：begin2，end2分别为叉树的后序序列在post[]中的开始位置（序号，数组下标+1）、结束位置； charr; inti;intm1;//中序序列中，左子树根位置 intm2;//后序序列中，左子树最后一个结点位置if(begin1-end1!=begin2-end2)returnERROR; if(end1-begin1>=0){ root=(BiTree)malloc(sizeof(BiTNode)); r=post[end2]; root->data=r;//根 for(i=begin1;i<=end1;i++) if(in[i]==r)break; m1=i-1; m2=begin2+i-begin1-1; root->lchild=NULL; root->rchild=NULL; if(createBiTree0120(root->lchild,in,begin1,m1,post,begin2,m2)==ERROR)//构造左子树 printf("初始化二叉树出错！\n\n请检查初始数据！\n\n"); if(createBiTree0120(root->rchild,in,m1+2,end1,post,m2+1,end2-1)==ERROR)//构造右子树 printf("初始化二叉树出错！\n\n请检查初始数据！\n\n");}else{ root=NULL;} returnOK;}voidgetDataFromFile0120(charfileName[],BiTree&root){//从文件fileName中读取数据构造二叉树root FILE*fp; charinOrder0120[100]; charpostOrder0120[100]; inta1,a2,b1,b2; fp=fopen(fileName,"r"); fscanf(fp,"%s\n",inOrder0120);fscanf(fp,"%s\n",postOrder0120); fclose(fp);a1=strlen("inOrder0120:");//中序序列第一个字符位置 a2=strlen(inOrder0120)-1;;//中序序列最后一个字符位置b1=strlen("postOrder0120:");//后序序列第一个字符位置 b2=strlen(postOrder0120)-1;//后序序列最后一个字符位置 if(createBiTree0120(root,inOrder0120,a1,a2,postOrder0120,b1,b2)==ERROR) printf("初始化二叉树出错！\n\n请检查初始数据！\n\n"); else printf("初始化二叉树成功！");}StatusPreOrder0120(BiTreep){//先序遍历二叉树if(p!=NULL){ printf("%c",p->data); PreOrder0120(p->lchild); PreOrder0120(p->rchild);} returnOK;}StatusInOrder0120(BiTreep){//中序遍历二叉树if(p!=NULL){ InOrder0120(p->lchild); printf("%c",p->data); InOrder0120(p->rchild);} returnOK;}StatusPostOrder0120(BiTreep){//后序遍历二叉树if(p!=NULL){ PostOrder0120(p->lchild); PostOrder0120(p->rchild); printf("%c",p->data);}returnOK;}StatusBTNodeDepth0120(BiTreep){//求二叉树的深度 intlchilddep,rchilddep; if(p==NULL) return0; else{lchilddep=BTNodeDepth0120(p->lchild);rchilddep=BTNodeDepth0120(p->rchild); return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1); } returnOK;}StatusLeafNodes0120(BiTreep,int*i){//求二叉树的叶子结点 intj; if(p!=NULL) { if(p->lchild!=NULL||p->rchild!=NULL) { j=*i; j++; *i=j; } LeafNodes0120(p->lchild,i); LeafNodes0120(p->rchild,i); returnOK; }}StatusBothNodes0120(BiTreep,int*i){//求度为2的结点数 intj; if(p!=NULL) { if(p->lchild!=NULL&&p->rchild!=NULL) { j=*i; j++; *i=j; } BothNodes0120(p->lchild,i); BothNodes0120(p->rchild,i); returnOK; }}六、实验环境1.环境：宿舍。2.硬件：2048M内存，500G硬盘。 3.系统：Windows764位操作系统4.软件平台：MicrosoftVisualC++6.0简体中文版七、相关文件列表如下demo.cpp:主程序文件bitree.cpp:操作实现的算法bitree.h：函数声明Mydef.h：存储结构的定义八、程序的运行测试及结果测试用例1：构造二叉树测试用例2：先序遍历测试用例3：中序遍历测试用例4：后序遍历测试用例