数据结构实验之求二叉树后序遍历和层次遍历

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;}