文档介绍：二叉树的基本操作实验报告
学号 姓名 实验日期 2012-12-26
实验室 计算机软件技术实验 指导教师 设备编号 401
实验内容 二叉树的基本操作
一 实验题目
实现二叉树的基本操作的代码实现
二 实验目的
iTree &root);
Status BothNodes0120 (BiTree p,int *i)//求度为2的结点数
5、给出操作实现的伪码
Status createBiTree0120 (BiTree &root,char in[],int begin1,int end1,char post[],int
begin2,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中读取数据构造二叉树root
FILE *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");
else
printf("初始化二叉树成功～");
}
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)