# 二叉树

```		    B
/  \
/    \
C      A
\
\
D
```

``````BCAD CBAD
ABDGKLRVWSXCEHMNFIOTUJPYQZ KGVRWLSXDBAMHNECTOUIFPYJZQ

``````

``````CDAB
KVWRXSLGDBMNHETUOIYPZQJFCA

``````

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct BiTNod
{
char data;
struct BiTNod *lchild,*rchild;
}BTNode;
BTNode *creatBT(char *pre,char *in,int n)/*/pre[]存放先序序列，in[]存放中序序列，n为二叉树的节点数*/
{
BTNode *s;
char *p;
int k;
if(n<=0)
return NULL;
s=(BTNode *)malloc(sizeof(BTNode));/*/创建二叉树节点*s*/
s->data =*pre;
for(p=in;p<in+n;p++)
{
if(*p==*pre)
break;
}
k=p-in;
s->lchild =creatBT(pre+1,in,k);
s->rchild =creatBT(pre+k+1,p+1,n-k-1);
return s;
}
int preorder_l(BTNode *T)/*后序输出*/
{
if(T!=NULL)
{
preorder_l(T->lchild );
preorder_l(T->rchild );
printf("%c",T->data );
}
return 0;
}
int main()
{
char pre[30],in[30];
int n;
while(scanf("%s%s",pre,in)!=EOF)
{
n=strlen(pre);
preorder_l(creatBT(pre,in,n));
printf("\n");
}
return 0;
}``````

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iomanip>
#include <algorithm>
#include <queue>
#define INF 100000000
#define MAX 550
#define MAXN 130
#define MOD 9
using namespace std;
char pre[30],in[30];
void solve(int preleft,int preright,int inleft,int inright)
{
int root,leftsize,rightsize;
for(root=inleft;root<=inright;root++)
if(pre[preleft]==in[root])
break;
leftsize=root-inleft;
rightsize=inright-root;
if(leftsize>0)
solve(preleft+1,preleft+leftsize,inleft,root-1);
if(rightsize>0)
solve(preleft+leftsize+1,preright,root+1,inright);
printf("%c",in[root]);
}
int main()
{
while(~scanf("%s%s",pre,in))
{
int n=strlen(pre);
solve(0,n-1,0,n-1);
printf("\n");
}
}
``````