/*
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入格式：两行，每行一个字符串，分别表示中序和后序排列

输出格式：一个字符串，表示所求先序排列

样例输入
BADC             ADEFGHMZ
BDCA    AEFDHZMG

样例输出
ABCD    GDAFEMHZ
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node//定义存储结构
{
    char data;
    struct node *lchild, *rchild;
};
char s1[50], s2[50];//s1指的是中序，s2指后序排列
struct node *creat(int length, char *s1, char *s2)//根据二叉树的后序序列和中序序列创建二叉树
{//s2存放后序序列,s1存放中序序列,length为二叉树结点个数
    int i;
    if(length == 0)//判断输入的字符是否为空
        return NULL;
    struct node *root;//定义一个指向node类型的指针root
    root = (struct node*)malloc(sizeof(struct node));//在内存中为root分配一个动态的存储空间
    root -> data = s2[length-1];//根结点的值
    for(i = 0; i < length; i++)//在中序序列中找等于根节点的位置i
    {
        if(s1[i] == root -> data)//如果中序排列中的元素与后序排列中最后一个元素相同，跳出循环；
            break;//这个相同元素则为根节点
    }
    root -> lchild = creat(i, s1, s2);//递归构造左子树 左子树节点个数，左中序，左后序
    root -> rchild = creat(length - i - 1, s1 + i + 1, s2 + i);//递归构造右子树 右子树节点个数，右中序，右后序
    return root;
}
void xianxv(struct node *root)
{
    if(root)
    {
        printf("%c", root -> data);
        xianxv(root -> lchild);
        xianxv(root -> rchild);
    }
}//先序遍历
int main()
{
 int length,m;
 int count=0;//定义一个计数器
 system("color 3F");//设置界面背景颜色
 printf("                        求先序序列    1604031045   朱涛               \n\n");
 printf("请输入中序序列:");
 scanf("%s",&s1);
 printf("\n");
 length = strlen(s1);//读取输入的字符串的长度
 if(length>8)//控制输入的字符长度
    {
        printf("输出字符超出字数限制，错误!!");
        return 0; //终止程序
    }
    for(m=0;m<length;m++)
    {
     if(s1[m]<'A'||s1[m]>'Z')
     {
      printf("第%d个字符输入存在非法字符，请输入大写字母\n",m+1);
   count++;//当检测到非法字符，计数器就自增
  }
 }
 if(count>0)
 return 0;
    printf("请输入后序序列:");
    scanf("%s",&s2);
    printf("\n");
    for(m=0;m<length;m++)
    {
     if(s2[m]<'A'||s2[m]>'Z')
     {
      printf("第%d个字符输入存在非法字符，请输入大写字母\n",m+1);
   count++;
  }
 }
 if(count>0)
 {
 return 0;
 }
    printf("先序序列为：");
    struct node *root;//定义一个root指针
    root = creat(length, s1, s2);//递归构造二叉树
    xianxv(root);
    printf("\n");
    return 0;
}