二叉树的基本操作实验报告学号姓名实验日期 2012-12-26实验室计算机软件技术实验指导教师设备编号 401实验内容二叉树的基本操作一实验题目实现二叉树的基本操作的代码实现二实验目的1、掌握二叉树的基本特性2、掌握二叉树的先序、中序、后序的递归遍历算法3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法三实习要求(1)认真阅读书上给出的算法(2)编写程序并独立调试四、给出二叉树的抽象数据类型ADT BinaryTree{//数据对象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、给出本数据的存储结构定义#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define NULL 0#define OVERFLOW -22、实现二叉树的抽象数据类型如下:typedef int Status;typedef char TElemType; 定义二叉树的数据元素类型为chr3、存储实现的抽象数据类型如下:typedef struct BiTNode0120{TElemType data;struct BiTNode0120 *lchild; // 左孩子指针struct BiTNode0120 *rchild;// 右孩子指针}BiTNode0120, *BiTree;4、运算的函数声明:Status CreateBiTree0120 (BiTree T, definition )//构建二叉树Status PreOrder0120 (BiTree p)//先序遍历Status InOrder0120 (BiTree p)//中序遍历Status PostOrder0120 (BiTree p)//后序遍历Status BTNodeDepth0120 (BiTree p)//求二叉树的深度Status LeafNodes0120 (BiTree p,int *i)//求二叉树叶子结点的个数void getDataFromFile0120(char fileName[],BiTree &root);Status BothNodes0120 (BiTree p,int *i)//求度为2的结点数5、给出操作实现的伪码Status createBiTree0120 (BiTree &root,char in[],int begin1,intend1,char post[],intbegin2,int end2){ //根据给定的中序序列in,后序序列post,构造二叉树root//其中: begin1，end1分别为叉树的中序序列在in[]中的开始位置(序号，数组下标+1)、结束位置;//其中: begin2，end2分别为叉树的后序序列在post[]中的开始位置(序号，数组下标+1)、结束位置;char r;int i;int m1; //中序序列中，左子树根位置int m2; //后序序列中，左子树最后一个结点位置if(begin1-end1!=begin2-end2) return ERROR;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;}return OK;}void getDataFromFile0120 (char fileName[],BiTree &root){ //从文件fileName中读取数据构造二叉树rootFILE *fp;char inOrder0120 [100];char postOrder0120 [100];int a1,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");elseprintf("初始化二叉树成功～");}Status PreOrder0120 (BiTree p){ // 先序遍历二叉树if ( p!= NULL ) {printf("%c", p->data);PreOrder0120 ( p->lchild ) ;PreOrder0120 ( p->rchild) ;}return OK;}Status InOrder0120 (BiTree p){ // 中序遍历二叉树if( p!= NULL ) {InOrder0120 ( p->lchild ) ;printf("%c", p->data);InOrder0120 ( p->rchild) ;}return OK;}Status PostOrder0120 (BiTree p){ // 后序遍历二叉树if ( p!= NULL ) {PostOrder0120 ( p->lchild ) ;PostOrder0120 ( p->rchild) ;printf("%c", p->data);}return OK;}Status BTNodeDepth0120 (BiTree p){//求二叉树的深度int lchilddep,rchilddep;if(p==NULL)return 0;else{lchilddep=BTNodeDepth0120 (p->lchild);rchilddep=BTNodeDepth0120 (p->rchild);return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);}return OK;}Status LeafNodes0120 (BiTree p,int *i){//求二叉树的叶子结点int j;if(p!=NULL){if(p->lchild!=NULL||p->rchild!=NULL){j = *i;j++;*i = j;}LeafNodes0120 (p->lchild,i);LeafNodes0120(p->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.环境:宿舍。