已知先序遍历和中序遍历求后序遍历

       输入一棵二叉树的先序遍历和中序遍历，输出它的后序遍历。

输入

输入有多组数据（少于100组），以文件结尾结束。
每组数据仅一行，包括两个字符串，中间用空格隔开，分别表示二叉树的先序序列和中序序列（字符串长度小于26，输入数据保证合法）。

输出

每组输出数据单独占一行，输出对应得后序序列。

样例输入

DBACEGF ABCDEFG

BCAD CBAD

样例输出

ACBFGED

CDAB

解析：

 题目给出了先序和中序遍历的字符串，按照先序的第一个元素在中序中找到相同的元素时，此时中序的左边元素归为左子树范围，右边元素归为右子树范围。以此分下去，具体代码如下

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//定义一个二叉树
typedef struct node
{
    char data;
    struct node *lchild,*rchild;//左孩子和右孩子
}STU;
//根据先序遍历和中序遍历建立出二叉树来
STU *tree(char *str1,char *str2,int len)//传先序遍历字符串和中序遍历字符串数组 和字符串长度两个一样长随便一个就可以
{
    int i;//for循环所需变量
    STU *heart;//定义头指针
    if(len==0)//长度为零返回空
        return NULL;
    heart=(STU *)malloc(sizeof(STU));//动态分配空间
    heart->data=str1[0];//先序的首元素做为节点
    //找到每一次的先序数组中头一个元素在中序中的位置
    for(i=0;i<len;i++)
        if(str1[0]==str2[i])
        break;
    //循环调用tree找左孩子和右孩子 得到二叉树
    heart->lchild=tree(str1+1,str2,i);
    heart->rchild=tree(str1+i+1,str2+i+1,len-i-1);
    return heart;
}
//从二叉树中找到后续遍历的结果保存到数组ret中
void printftree(STU *heart,char ret[],int *cnt)//*cnt是用作计数器记数组ret的下标
{
    if(heart!=NULL)//树不为空
    {
        //循环调用实现后续遍历
        printftree(heart->lchild,ret,cnt);
        printftree(heart->rchild,ret,cnt);
        ret[(*cnt)++] = heart->data;//将遍历的结果存入数组是以一个字符一个字符的存进去
    }


}
int main ()
{
    char str1[27],str2[27];
    char ret[100][27];//定义100个一次可存27个字符的静态空间
    int len;//接收字符串长度
    STU *heart;//接收返回的heart头指针的指针变量
    int len2 = 0;//数组ret组数的计数器
    int cnt ;//数组ret一组字符长度的计数器
    while(scanf("%s%s",str1,str2)!=EOF)
    {
        len=strlen(str1);
        heart=tree(str1,str2,len);
        cnt = 0;
        printftree(heart,ret[len2],&cnt);//传树头结点和ret[0] 还有计数器cnt
        ret[len2][cnt] = NULL;//存后序遍历结果的数组以NULL结尾
        len2 ++;
    }
    int i = 0;
    for(;i<len2;i++){
        printf("%s\n",ret[i]);//输出所有组 后序遍历结果
    }
    return 0;
}