YTU 3025: 创建二叉树

3025: 创建二叉树

时间限制:  1 Sec   内存限制:  128 MB

提交: 

3   解决:  3

题目描述

已知一颗二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，给出二叉树的树形表示（用括号法）。

输入

输出

输出带有括号与字母的用括号法表示的二叉树。

提示

首先根据中序序列和后序序列画出二叉树，然后用括号法表示之。

利用中序序列与后序序列构造二叉树，然后采用括号表示法输出！

AC代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Node
{
char data;
Node *lc;
Node *rc;
} Node;
Node *CreateBT2(char *post,char *in,int n)
{
Node *b;
int r,k;
char *p;
if(n<=0)return NULL;
r=*(post+n-1); //定位到当前区间最后一个地址，根节点
b=(Node*)malloc(sizeof(Node));
b->data=r; //开始创建
for(p=in; p<in+n; p++)
if(*p==r)break;
k=p-in; //定位根节点在中序遍历中的位置
b->lc=CreateBT2(post,in,k);
b->rc=CreateBT2(post+k,p+1,n-k-1);
return b;
}
void Print(Node *b)
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lc!=NULL||b->rc!=NULL)
{
printf("(");
Print(b->lc);
if(b->rc!=NULL)printf(",");
Print(b->rc);
printf(")");
}
}
}
int main()
{
int len;
Node *head;
char post[30]="cedbhjigfa",in[30]="cbedahgijf"; // 存储先序和中序遍历的序列
head=(Node*)malloc(sizeof(Node));
len=strlen(post);
head=CreateBT2(post,in,len); //构造二叉树
Print(head); //用括号表示法输出二叉树
return 0;
}