3.4.2 American Heritage 美国血统

3.4.2 American Heritage 美国血统

```                  C
/   \
/     \
B       G
/ \     /
A   D   H
/ \
E   F

```

``````ABEDFCHG

``````AEFDBHGC
``````

``````#include <stdio.h>
#include <string.h>
char a[30],b[30];
int len,cnt;
void solve(int s,int e){
int i;
if(s==e || cnt==len)
return ;
/*if(s==e-1){
printf("%c",a[s]);
return ;
}*/
for(i=s;i<e;i++){
if(a[i]==b[cnt])
break;
}
if(s<i){
cnt++;
solve(s,i);
}
if(i<e-1){
cnt++;
solve(i+1,e);
}
printf("%c",a[i]);
}

int main(){
while(scanf("%s%s",a,b)!=EOF){
len=strlen(a);
cnt=0;
solve(0,len);
printf("\n");
}
return 0;
}``````

``````#include<stdio.h>
#include<string.h>
char a[1000];
char b[1000];
int n;
int search(int x1,int y1,int x2,int y2)
{
if(x1>y1)
{
return 0;
}
else if(x1==y1)
{
printf("%c",a[x1]);
return 0;
}
else
{
int mid;
for(int i=x2;i<=y2;i++)//寻找分割点
{
if(b[i]==a[x1])
mid=i;
}
search(x1+1,x1+mid-x2,x2,mid-1);
search(x1+mid-x2+1,y1,mid+1,y2);
printf("%c",a[x1]);//a[x1]表示首节点
}
}
int main()
{
gets(b);
gets(a);
n=strlen(a);
search(0,n-1,0,n-1);
} ``````