题目链接：http://poj.org/problem?id=2255
思路分析：根据先序遍历（如DBACEGF）可以找出根结点(D)，其后为左右子树；根据中序遍历（如ABCDEFG），已知根结点(D),
可以知道在根结点左边的为左子树结点（ABC），右边为右子树结点（EFG）；可以求出左子树与右子树结点个数；已知道左右子树
结点个数（分别为3个），根据先序遍历（如DBACEGF）可知其左子树的先序遍历（BAC）与右子树的先序遍历（EGF）；左右子树
的先序遍历与中序遍历可知，递归构造树再后序遍历求解。
代码如下：
#include <iostream>
#include <string>
using namespace std; struct TreeNode;
typedef TreeNode *SearchTree;
typedef char ElementType;
struct TreeNode
{
ElementType Element;
SearchTree Left;
SearchTree Right;
}; void PostOrder(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree CreateTree(string PreOrder, string InOrder, SearchTree T); int main()
{
string PreOrder, InOrder; while (cin >> PreOrder >> InOrder)
{
SearchTree T = NULL; T = CreateTree(PreOrder, InOrder, T);
PostOrder(T);
cout << endl;
} return ;
} SearchTree Insert(ElementType X, SearchTree T)
{
if (T == NULL)
{
T = (SearchTree)malloc(sizeof(struct TreeNode));
if (T == NULL)
{
printf("Out of space");
return NULL;
}
T->Element = X;
T->Left = T->Right = NULL;
}
else
if (X < T->Element)
T->Left = Insert(X, T->Left);
else
if (X > T->Element)
T->Right = Insert(X, T->Right); return T;
} void PostOrder(SearchTree T)
{
if (T != NULL)
{
PostOrder(T->Left);
PostOrder(T->Right);
printf("%c", T->Element);
}
} SearchTree CreateTree(string PreOrder, string InOrder, SearchTree T)
{
int Index;
char Root; if (PreOrder.length() > )
{
Root = PreOrder[];
T = Insert(Root, T); Index = InOrder.find(Root);
T->Left = CreateTree(PreOrder.substr(, Index), InOrder.substr(, Index), T->Left);
T->Right = CreateTree(PreOrder.substr(Index + ), InOrder.substr(Index + ), T->Right);
} return T;
}