二叉樹前序、中序、后序遍歷相互求法

FtpListALL(FTP列表遍歷軟件)v1.14 中文綠色版

• 類型：FTP 工具大�。�106KB語言：中文 評分：5.0
• 標簽：

立即下載

今天來總結(jié)下二叉樹前序、中序、后序遍歷相互求法，即如果知道兩個的遍歷，如何求第三種遍歷方法，比較笨的方法是畫出來二叉樹，然后根據(jù)各種遍歷不同的特性來求，也可以編程求出，下面我們分別說明。

首先，我們看看前序、中序、后序遍歷的特性： 
前序遍歷： 
    1.訪問根節(jié)點 
    2.前序遍歷左子樹 
    3.前序遍歷右子樹 
中序遍歷： 
    1.中序遍歷左子樹 
    2.訪問根節(jié)點 
    3.中序遍歷右子樹 
后序遍歷： 
    1.后序遍歷左子樹 
    2.后序遍歷右子樹 
    3.訪問根節(jié)點

一、已知前序、中序遍歷，求后序遍歷

例：

前序遍歷:         GDAFEMHZ

中序遍歷:         ADEFGHMZ

畫樹求法：
第一步，根據(jù)前序遍歷的特點，我們知道根結(jié)點為G

第二步，觀察中序遍歷ADEFGHMZ。其中root節(jié)點G左側(cè)的ADEF必然是root的左子樹，G右側(cè)的HMZ必然是root的右子樹。

 第三步，觀察左子樹ADEF，左子樹的中的根節(jié)點必然是大樹的root的leftchild。在前序遍歷中，大樹的root的leftchild位于root之后，所以左子樹的根節(jié)點為D。

第四步，同樣的道理，root的右子樹節(jié)點HMZ中的根節(jié)點也可以通過前序遍歷求得。在前序遍歷中，一定是先把root和root的所有左子樹節(jié)點遍歷完之后才會遍歷右子樹，并且遍歷的左子樹的第一個節(jié)點就是左子樹的根節(jié)點。同理，遍歷的右子樹的第一個節(jié)點就是右子樹的根節(jié)點。

第五步，觀察發(fā)現(xiàn)，上面的過程是遞歸的。先找到當前樹的根節(jié)點，然后劃分為左子樹，右子樹，然后進入左子樹重復(fù)上面的過程，然后進入右子樹重復(fù)上面的過程。最后就可以還原一棵樹了。該步遞歸的過程可以簡潔表達如下：

1 確定根,確定左子樹，確定右子樹。

2 在左子樹中遞歸。

3 在右子樹中遞歸。

4 打印當前根。

那么，我們可以畫出這個二叉樹的形狀：

那么，根據(jù)后序的遍歷規(guī)則，我們可以知道，后序遍歷順序為：AEFDHZMG

編程求法：（依據(jù)上面的思路，寫遞歸程序）

 1 #include <iostream>  
 2 #include <fstream>  
 3 #include <string>  
 4 
 5 struct TreeNode
 6 {
 7   struct TreeNode* left;
 8   struct TreeNode* right;
 9   char  elem;
10 };
11 
12 void BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
13 {
14   if(length == 0)
15     {
16       //cout<<"invalid length";
17       return;
18     }
19   TreeNode* node = new TreeNode;//Noice that [new] should be written out.
20   node->elem = *preorder;
21   int rootIndex = 0;
22   for(;rootIndex < length; rootIndex++)
23     {
24       if(inorder[rootIndex] == *preorder)
25       break;
26     }
27   //Left
28   BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);
29   //Right
30   BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
31   cout<<node->elem<<endl;
32   return;
33 }
34 
35 
36 int main(int argc, char* argv[])
37 {
38     printf("Hello World!\n");
39     char* pr="GDAFEMHZ";
40     char* in="ADEFGHMZ";
41   
42     BinaryTreeFromOrderings(in, pr, 8);
43 
44     printf("\n");
45     return 0;
46 }

輸出的結(jié)果為：AEFDHZMG

二、已知中序和后序遍歷，求前序遍歷

依然是上面的題，這次我們只給出中序和后序遍歷：

中序遍歷:       ADEFGHMZ

后序遍歷:       AEFDHZMG

畫樹求法：
第一步，根據(jù)后序遍歷的特點，我們知道后序遍歷最后一個結(jié)點即為根結(jié)點，即根結(jié)點為G。

第二步，觀察中序遍歷ADEFGHMZ。其中root節(jié)點G左側(cè)的ADEF必然是root的左子樹，G右側(cè)的HMZ必然是root的右子樹。

第三步，觀察左子樹ADEF，左子樹的中的根節(jié)點必然是大樹的root的leftchild。在前序遍歷中，大樹的root的leftchild位于root之后，所以左子樹的根節(jié)點為D。

第四步，同樣的道理，root的右子樹節(jié)點HMZ中的根節(jié)點也可以通過前序遍歷求得。在前后序遍歷中，一定是先把root和root的所有左子樹節(jié)點遍歷完之后才會遍歷右子樹，并且遍歷的左子樹的第一個節(jié)點就是左子樹的根節(jié)點。同理，遍歷的右子樹的第一個節(jié)點就是右子樹的根節(jié)點。

第五步，觀察發(fā)現(xiàn)，上面的過程是遞歸的。先找到當前樹的根節(jié)點，然后劃分為左子樹，右子樹，然后進入左子樹重復(fù)上面的過程，然后進入右子樹重復(fù)上面的過程。最后就可以還原一棵樹了。該步遞歸的過程可以簡潔表達如下：

1 確定根,確定左子樹，確定右子樹。

2 在左子樹中遞歸。

3 在右子樹中遞歸。

4 打印當前根。

這樣，我們就可以畫出二叉樹的形狀，如上圖所示，這里就不再贅述。

那么，前序遍歷:         GDAFEMHZ

編程求法：（并且驗證我們的結(jié)果是否正確）

#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;
}

輸出結(jié)果：GDAFEMHZ