利用二叉树中序及先序遍历确定该二叉树的后序序列

 1000(ms)

 10000(kb)

 2708 / 5517

已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历，但已知先序和后序，却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果，要求输出其后序遍历结果。

输入

输入数据占2行，其中第一行表示中序遍历结果，第二行为先序遍历结果。

输出

对测试数据，输出后序遍历结果。

样例输入

BFDAEGC
ABDFCEG

样例输出

FDBGECA

 

 

#include<stdio.h>
#include<malloc.h>
#include<string.h>
struct BTNode
{
    char data;
    struct BTNode *lchild;
    struct BTNode *rchild;
};
struct BTNode *CreateBT1(char *pre,char *in,int n)
{
    BTNode *b;
    char *p;
    int k;
    if(n<=0) return NULL;
    b=(BTNode *)malloc(sizeof(BTNode));
    b->data=*pre;//先序遍历中根结点储存的字符或者双亲结点储存的字符 
    for(p=in;p<in+n;p++)//在中序遍历中找到该字符的位置 
        if(*p==*pre) break;
    k=p-in;//用k储存长度 
    b->lchild=CreateBT1(pre+1,in,k);//将中序的左边变为左孩子 
    b->rchild=CreateBT1(pre+k+1,p+1,n-k-1);//将中序的右边变为右孩子 
    return b;
}
void PostOrder(struct BTNode *p)//后序遍历输出二叉树 
{
    if(p!=NULL)
    {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        printf("%c",p->data);
    }
}
int main()
{
    char *pre,*in;
    int n;
    char a[100],b[100];
    scanf("%s",a);
    scanf("%s",b);
    n=strlen(a);
    in=a;//指向a数组第一个字符 
    pre=b;//指向b数组第一个字符 
    PostOrder(CreateBT1(pre,in,n));
}