題意：輸入兩組數據，分別是前序遍歷序列和中序遍歷序列，你需要編寫程序通過這兩組數據求出該樹的後序遍歷序列（前序序列 + 中序序列 = 後序序列）
解法：遞歸
題目分析：
可以先按照用筆和紙的形式去推導出後序序列。推導過程省略，在推導過程中我們會發現規律：
假設 前序序列是 A B E H F C G I
中序序列是 H E B F A C I G （圖如下）
每一次從前序序列裡，按順序抽取出字母就能將中序序列分割，並根據中序遍歷的特性。分割後的兩部分分別是 左子樹 和 右子樹（注意，他們也是二叉樹！）
就像這樣：取A， 中序序列被分割為 左子樹：H E B F 右子樹 C I G
繼續取B，但是這次是對左子樹：H E B F 進行分割。 分割結果是： 左子樹：H E 右子樹 B F
直到不能再分割，遞歸會返回去到第一次使用 A 分割出來的 右子樹 裡繼續分割
上述整個過程都是遞歸，所以結合代碼和用紙筆畫一次會更好理解
代碼：
[cpp]
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode
{
char data;
struct TreeNode *lchild;
struct TreeNode *rchild;
} Node, *PNode;
char preorder[28]; //存放前序序列
char infix[28]; //存放中序序列
char *Pr;
void build(char *in, char *pr, PNode *tr);
void postordertraversal(PNode T);
int main()
{
//先建樹、再後序遍歷輸出
PNode T;
while(scanf("%s %s", &preorder[1], &infix[1]) == 2)
{
build(&infix[1], &preorder[1], &T);
postordertraversal(T);
printf("\n");
}
return 0;
}
void build(char *in, char *pr, PNode *tr)
{
char *p = in;
Pr = pr;
if (*in == 0)
{
*tr = NULL;
return;
}
while (1)
{
if (*in == *Pr)
{
(*tr) = (PNode)malloc(sizeof(Node));
(*tr)->data = *Pr;
*in = 0;
break;
}
in++;
}
Pr = Pr + 1;
build(p, Pr, &(*tr)->lchild);
build(in+1, Pr, &(*tr)->rchild);
}
void postordertraversal(PNode T)
{
if (T == NULL)
return;
postordertraversal(T->lchild);
postordertraversal(T->rchild);
printf("%c", T->data);
}
這份代碼有些東西需要注意：
這裡使用到指針，其實可以不使用指針的，下面介紹的更精巧的解法就是用下標的。能盡量不用指針就盡量不用
注意指向指針的指針在這裡的作用，這裡有講解
上面的解法是比較直接容易想到的，所以代碼沒有很精巧。而這裡有份更好的解法！
