学步园

//http://acm.pku.edu.cn/JudgeOnline/problem?id=2255

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
char preorder[30];
char inorder[30];
typedef struct _node
{
    char
val;   
    struct _node
*left;
    struct _node
*right;
}node;
struct _node* root;
struct _node* mk_tree(char *pre,char *in,int n)//递归建树，注意返回的是节点指针

{
    struct
_node* r=NULL;
   
if(n>0)
    {
   
    r=(struct
_node*)malloc(sizeof(struct _node));
   
   
r->val=*pre;
   
    int i;
   
    char
*p=in;
   
   
for(i=0;i<n;i++,p++)
   
   
   
if(*p==*pre)break;

   
   
r->left=mk_tree(pre+1,in,i);
   
   
r->right=mk_tree(pre+i+1,in+i+1,n-i-1);   
    }
    return
r;
}

void postorder(struct _node* r)//后根遍历

{
   
   
if(r==NULL)return;
   
postorder(r->left);   
   
postorder(r->right);
   
printf("%c",r->val);

}

int main()
{
   
while(cin>>preorder>>inorder)   
   
    {
   
    struct
_node* root=mk_tree(preorder,inorder,strlen(preorder));
   
   
postorder(root);
   
   
printf("/n");
    }
    return
0;
}