PRoblem Description

已知一棵二叉樹的前序遍歷和中序遍歷，求二叉樹的后序遍歷和層序遍歷。

Input

輸入數據有多組，第一行是一個整數t (t<1000)，代表有t組測試數據。每組包括兩個長度小于50 的字符串，第一個字符串表示二叉樹的先序遍歷序列，第二個字符串表示二叉樹的中序遍歷序列。

Output

每組第一行輸出二叉樹的后序遍歷序列，第二行輸出二叉樹的層次遍歷序列。

Example Input

2abdegcfdbgeafcxnliulnixu
Example Output
dgebfcaabcdefglinuxxnuli
 
#include<stdio.h>#include<string.h>#include<stdlib.h>#define maxsize 50typedef struct node{    char data;    struct node *lc,*rc;}bitree;bitree * queue[51];int front=0,rear=0;bitree * create(int zlen,char qst[],char zst[]){    if(zlen<=0)        return NULL;    int i;    bitree *t;    t=(bitree *)malloc (sizeof(bitree));    t->data=qst[0];    for(i=0;i<zlen;i++)    {        if(qst[0]==zst[i])            break;    }    t->lc=create(i,qst+1,zst);    t->rc=create(zlen-i-1,qst+i+1,zst+i+1);    return t;}void postshow(bitree * tree){    bitree * t;    t=tree;    if(t)    {        postshow(t->lc);        postshow(t->rc);        printf("%c",t->data);    }}void enter_queue(bitree *t){    if((rear+1)%maxsize!=front)    {        rear=(rear+1)%maxsize;        queue[rear]=t;    }}bitree *delete_queue(){    if(front!=rear)    {        front=(front+1)%maxsize;        return queue[front];    }}void level_order(bitree *t){    bitree *p;    if(t)    {        enter_queue(t);        while(rear!=front)        {            p=delete_queue();            printf("%c",p->data);            if(p->lc)            {                enter_queue(p->lc);            }            if(p->rc)            {                enter_queue(p->rc);            }        }    }}int main(){    int zlen,t;    char qst[51],zst[51];    bitree * tree;    scanf("%d",&t);    while(t--)    {        scanf("%s%s",qst,zst);        zlen=strlen(zst);        tree=create(zlen,qst,zst);        postshow(tree);        printf("/n");        level_order(tree);        printf("/n");    }    return 0;}