问题：
两个字符串，其长度n均小于等于26。
第一行为前序遍历，第二行为中序遍历。
二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。
输出：
输入样例可能有多组，对于每组测试样例，
输出一行，为后序遍历的字符串。
例如：
ABC
CBA
ABCDEFG
DCBAEFG
输出：
CBA
DCBGFEA
分析：
1，先需要根据先序和中序得到一个唯一的二叉树，所以首先进行二叉树的创建
2，二叉树创建
先序：ABCDEFG,其中，A就是二叉树的根节点，存储到二叉树根节点中
中序：DCBAEFG,中序是左-根-右，找到A中根节点在中序中的位置，其中DCB就是中序的左子树ml，EFG就是中序的右子树mr
根据中序可以知道先序中BCD是先序的左子树pl，EFG是先序的右子树pr
然后进行递归，pl和ml，pr和mr
递归退出条件是当前序的长度<=0,返回NULL，否则返回T
创建二叉树：
Node* create_tree(string p,string m){ //p是前序字符串，m是中序字符串
if(p.size()<=0) return NULL;
Tree *t=new Tree;
t->data=p[0];
string pl,pr,ml,mr;
int index=m.find(p[0]);//获取根节点在中序序列中的位置
pl=p.substr(1,index);
pr=p.substr(index+1);
ml=m.substr(0,index);
mr=m.substr(index+1);
t->lchild=create_tree(pl,ml);
t->rchild=create_tree(pr,mr);
return t;
}
完整代码：
#include <iostream>
#include <string>
using namespace std;
//定义一个二叉树的结构体
typedef struct Tree{
char data;
struct Tree *lchild;
struct Tree *rchild;
};
Tree* create_Tree(string p,string m){
if(p.size()<=0){
return NULL;
}
Tree *t=new Tree;
t->data=p[0]; //插入根元素
//得到根元素在中序序列中的下标
int index=m.find(p[0]);
//cout<<index<<endl;
string pl,pr,ml,mr;//定义前序中的左子树序列，右子树序列pl,pr，定义中序序列中的左子树序列，右子树序列ml，mr
pl=p.substr(1,index);
pr=p.substr(index+1);
ml=m.substr(0,index);
mr=m.substr(index+1);
t->lchild=create_Tree(pl,ml);
t->rchild=create_Tree(pr,mr);
return t;
}
void hou_tree(Tree *&t){
if(t){
hou_tree(t->lchild);
hou_tree(t->rchild);
cout<<t->data;
}
}
int main()
{
string p1,m1;//p1是前序序列，m1是中序
//前序和中序决定一个二叉树，并输出后序遍历
while(cin>>p1>>m1){
Tree *t=create_Tree(p1,m1); //根据前序和中序创建二叉树
hou_tree(t);
cout<<endl;
}
return 0;
}
结果截图：
