先序中序後序

二叉樹的周遊方法有先序中序後序三種方法，先以下圖為例解釋三種周遊順序：

所謂的先後中都是以父節點為中心出發的，即

先序為：父節點、左子節點、右子節點；(父節點第一個)

中序為：左子節點、父節點、右子節點；（父節點放中間，第二個）

後序為：左子節點、右子節點、父節點；（父節點最後一個）

以上圖為例，

先序周遊順序為：GDAFEMHZ

中序周遊順序為：ADEFGHMZ

後序周遊順序為：AEFDHZMG

在此三種周遊順序的基礎上，已知中序和另外一種周遊即可擷取第三種周遊順序，即中序周遊+任意一種周遊順序确定一棵二叉樹。

已知先序中序

先序周遊第一個總是根節點，中序周遊根節點總在左子樹和右子樹中間。是以，先序的第一個數就是根節點，然後在中序中找到該根節點，左邊為左子樹，右邊為右子樹。接着再分别拿左子樹右子樹來判斷後續，原理同上。

找到一個算法：

#include <iostream>  
 #include <fstream>  
 #include <string>  
 
 struct TreeNode
 {
   struct TreeNode* left;
   struct TreeNode* right;
   char  elem;
 };
 
 void BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
 {
   if(length == 0)
     {
       //cout<<"invalid length";
       return;
     }
   TreeNode* node = new TreeNode;//Noice that [new] should be written out.
   node->elem = *preorder;
   int rootIndex = 0;
   for(;rootIndex < length; rootIndex++)
     {
       if(inorder[rootIndex] == *preorder)
       break;
     }
   //Left
   BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);
   //Right
   BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
   cout<<node->elem<<endl;
   return;
 }
 
 
 int main(int argc, char* argv[])
 {
     char* pr="GDAFEMHZ";
     char* in="ADEFGHMZ";
   
     BinaryTreeFromOrderings(in, pr, 8);
     printf("\n");
     return 0;
 }
           

已知後序中序

後序周遊最後一個數總是根節點，中序周遊根節點總在左子樹和右子樹中間。是以，後序的最後一個數就是根節點，然後在中序中找到該數，左邊為左子樹，右邊為右子樹。接着再分别拿左子樹和右子樹按上述方法周遊。

算法如下：

#include <iostream>
#include <fstream>
#include <string>

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char  elem;
};


TreeNode* BinaryTreeFromOrderings(char* inorder, char* aftorder, int length)
{
    if(length == 0)
    {
        return NULL;
    }
    TreeNode* node = new TreeNode;//Noice that [new] should be written out.
    node->elem = *(aftorder+length-1);
    std::cout<<node->elem<<std::endl;
    int rootIndex = 0;
    for(;rootIndex < length; rootIndex++)//a variation of the loop
    {
        if(inorder[rootIndex] ==  *(aftorder+length-1))
            break;
    }
    node->left = BinaryTreeFromOrderings(inorder, aftorder , rootIndex);
    node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, aftorder + rootIndex , length - (rootIndex + 1));
    
    return node;
}

int main(int argc, char** argv)
{
    char* af="AEFDHZMG";    
    char* in="ADEFGHMZ"; 
    BinaryTreeFromOrderings(in, af, 8); 
    printf("\n");
    return 0;
}
           

注意，已知先序和後序不能唯一确定該二叉樹，即不能求出中序周遊順序。