题目描述
知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及后序遍历结果,要求输出其先序遍历结果。
输入
第一行为中序序列 第二行为后续序列
输出
输出为遍历二叉树得到的先序序列
样例输入
BFDAEGC
FDBGECA
样例输出
ABDFCEG
参考程序
#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef struct node
{
char data;
struct node*lchild,*rchild;
}BTnode;
BTnode *create(char *post,char *in,int n)
{
BTnode *b;
char *p,r;
int k;
if(n<=0)
return NULL;
r=*(post+n-1);
b=(BTnode *)malloc(sizeof(BTnode));
b->data=r;
for(p=in;p<in+n;p++)
{
if(*p==r)
break;
}
k=p-in;
b->lchild=create(post,in,k);
b->rchild=create(post+k,p+1,n-k-1);
return b;
}
void Pre(BTnode *b)
{
if(b!=NULL)
{
printf("%c",b->data);
Pre(b->lchild);
Pre(b->rchild);
}
}
int main()
{
char post[100],in[100];
BTnode *b;
int n;
scanf("%s",in);
scanf("%s",post);
n=strlen(post);
b=create(post,in,n);
Pre(b);
return 0;
}
注意
该程序仅供学习参考!