【題目】輸入某二叉樹的前序周遊和中序周遊的結果，請重建出該二叉樹，假設輸入的前序周遊和中序周遊的結果中都不含有重複的數字，例如輸入前序周遊序列｛1，2，4，7，3，5，6，8｝和中序周遊序列｛4，7，2，1，5，3，8，6｝，重建二叉樹并輸出頭結點。
【分析】對根節點和左子樹右子樹分别分析
【根節點】前序周遊結果和中序周遊結果可以唯一确定一棵二叉樹，前序周遊的過程就是從根結點開始，先通路根結點，再周遊左子樹，最後右子樹，從｛1，2，4，7，3，5，6，8｝可以看出1為根節點，中序周遊的過程是先周遊左子樹，通路根節點，最後周遊右子樹，從｛4，7，2，1，5，3，8，6｝就知道｛4，7，2｝，{5，3，8，6｝分别為根節點1的左子樹和右子樹，分别分析左子樹和右子樹。
【左子樹】此時變成前序周遊序列｛2，4，7｝，中序周遊序列｛4，7，2｝，則對這個分支來說，2就是根節點1的左孩子，是4，7的父結點，也就是左子樹分支的根結點，從｛4，7，2｝可以看出，｛4，7｝是結點2的左子樹，結點2沒有右子樹，是以去除根節點2，考慮｛4，7｝，很顯然由前序序列｛4，7｝，得到4作為根節點，但是從中序周遊序列看｛4，7｝，7在4的右側，說明4沒有左子樹，7是其右子樹，隻有7一個，是以，結點7為4的右孩子。整個以根節點1的左子樹分析完畢。
【右子樹】前序序列｛3，5，6，8｝，中序序列｛5，3，8，6｝，根節點為3，是以｛5｝，｛8，6｝分别為其左右子樹，左子樹隻有｛5｝是以結點5為3的左孩子，右子樹前序為｛6，8｝中序為｛8，6｝，根節點為6，剩下的8就是它的左孩子。整個以根節點1的右子樹分析完畢。
【流程圖】
将分析過程用下圖來直覺分析，始終變動的是root，相對各結點的子樹作為根節點的變化情況，看圖會更清晰，有助于對程式的了解。子樹排列為左子樹在左邊，右子樹在右邊。
【二叉樹重建圖】
最終得到的二叉樹如圖所示：
【測試代碼】
#include<stdio.h>
#include<stdlib.h>
typedef struct BiTreeNode
{
int data;
struct BiTreeNode *left, *right;
}Node_t;
Node_t *construct(int *startPreorder, int *endPreorder, int *startInorder, int *endInorder)
{
//前序周遊确定根節點
int rootValue= startPreorder[];
Node_t *root =(Node_t *)malloc(sizeof(Node_t));
root->data = rootValue;
root ->left = root ->right = NULL;
if(startPreorder == endPreorder)
{
if( startPreorder == endInorder && *startPreorder == *startInorder )
return root;
}
//中序周遊确定左子樹，右子樹
int *rootInorder = startInorder;
while(rootInorder <= endInorder && *rootInorder != rootValue)
++rootInorder;
if(rootInorder == endInorder && *rootInorder != rootValue)
{
printf("Invalid input");
return NULL;
}
int left_length = rootInorder - startInorder;
int *left_Preorder_End = startPreorder + left_length;
if(left_length>)
{
//rebuild left tree
root ->left = construct(startPreorder+, left_Preorder_End, startInorder, rootInorder-);
}
if(left_length < endPreorder - startPreorder)
{
//rebuild right tree
root ->right = construct(left_Preorder_End+ , endPreorder, rootInorder+, endInorder);
}
return root;
}
Node_t *create(int *preorder, int *inorder, int length)
{
if( preorder == NULL || inorder == NULL || length <= )
return NULL;
return construct(preorder, preorder + length -, inorder, inorder + length -);
}
//後序周遊
void post_order_visit(Node_t **T)
{
if(*T == NULL)
return ;
else
{
post_order_visit(&(*T)->left);
post_order_visit(&(*T)->right);
printf("%d ",(*T)->data);
}
}
int main()
{
int pre_visit[] = {, , , , , , , };
int in_visit[] = {, ,, , , , , };
int *preorder = pre_visit;
int *inorder = in_visit;
Node_t *root =create(preorder, inorder, );
post_order_visit(&root);
return ;
}
【輸出結果】
程式參考劍指offer面試6裡所給程式，實作的思路符合上述分析過程，是以有助于了解，從單步調試過程可以發現所建二叉樹正确無誤，在測試過程中分别測試以下幾個方面，才能決定程式的可靠性全面性，
1.普通例子，如測試用例中給出的序列；
2.特殊例子，隻有一個根節點，或所有節點都隻有左節點或右結點，或者沒有結點；
3.輸入的前序和中序不比對；分析一下前序和中序不比對可能存在的問題，二者有一個正确，一個錯誤，可能是排序序列錯誤，輸入長度錯誤，比如說中序錯誤中間某兩個元素換位了，在上述步驟運作下會産生異常，進而抛出invalid input，由于c語言沒有異常處理，隻能傳回異常代碼，但是c++有恰當的機制來解決，這一點可以檢視c++文檔。
【二叉樹重建延伸】
如果已知後序和中序序列，重建二叉樹，中序序列{4，7，2，1，5，3，8，6}，後序序列｛7，4，2，5，8，6，3，1｝
【分析+流程圖】
由後序序列可以始終确定最後一位一定是二叉樹的根root，由中序序列可以确定左子樹成分和右子樹成分，據此，利用流程圖進行分析，
分析過程類似于前序序列和中序序列重建二叉樹過程。