二叉树遍历：有先序和中序，输出它的广度优先遍历序列

Question

输入格式
第一行为一个整数t（0<t<10），表示测试用例个数。 以下t行，每行输入一个测试用例，包含两个字符序列s1和s2，其中s1为一棵二叉树的先序遍历序列，s2为中序遍历序列。s1和s2之间用一个空格分 隔。序列只包含大写字母，并且每个字母最多只会出现一次。

输出格式
为每个测试用例单独一行输出广度优先遍历序列。

样例输入
2
DBACEGF ABCDEFG
BCAD CBAD
样例输出
DBEACGF
BCAD

Answer 1

广度优先遍历是后续遍历吧……
写了个小程序，你看看
#include<iostream>
using namespace std;
#define n 8
typedef struct node
{
char data;
struct node * left;
struct node * right;
}Node;

char post[n]={'g','d','b','e','h','f','c','a'};
char ino[n]={'d','g','b','a','e','c','h','f'};

Node *findchild(char *a,int i1,int j1,char *b,int i2,int j2)
{
if(i1>j1||i2>j2) return NULL;

Node *p=new Node;
int i;
p->data=a[j1];
for(i=i2;i<=j2;i++)
{
if(b[i]==a[j1])break;
}
p->left=findchild(a,i1,i1+i-i2-1,b,i2,i-1);
p->right=findchild(a,i1+i-i2,j1-1,b,i+1,j2);
return p;
}

void preorder(Node *t)
{
if(t!=NULL)
{
cout<<t->data<<" ";
preorder(t->left);
preorder(t->right);
}
}

int main()
{
Node *head,*t;
head=findchild(post,0,n-1,ino,0,n-1);
t=head;
preorder(t);
cout<<endl;
system("pause");
return 0;
}追问

先谢啦

Answer 2

迎喜迎春迎富贵 接财接福接平安 横批：吉祥如意