IT工程師數位筆記本

最近參加一些筆試發現，很多公司喜歡考二叉樹前序、中序、后序遍歷相互求法，即如果知道兩個的遍歷，如何求第三種遍歷方法，今天總結來總結一下。有兩種方法：比較笨的方法是畫出來二叉樹，然后根據各種遍歷不同的特性來求；也可以編程求出。下面先對畫樹方法進行說明，以了解原理。

首先，我們看看前序、中序、后序遍歷的特性： 
前序遍歷： TLR  (規律：根在前；子樹在根后且左子樹比右子樹靠前)；

    1.訪問根節點 
    2.前序遍歷左子樹 
    3.前序遍歷右子樹 

中序遍歷： LTR  (規律：根在中；左子樹在跟左邊，右子樹在根右邊)；

    1.中序遍歷左子樹 
    2.訪問根節點 
    3.中序遍歷右子樹 

后序遍歷：LRT  (規律：根在后；子樹在根前且左子樹比右子樹靠前)；

    1.后序遍歷左子樹 
    2.后序遍歷右子樹 
    3.訪問根節點

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

例：

前序遍歷:         GDAFEMHZ

中序遍歷:         ADEFGHMZ

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

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

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

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

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

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

2 在左子樹中遞歸。

3 在右子樹中遞歸。

4 打印當前根。

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

那么，根據后序的遍歷規則，我們可以知道，后序遍歷順序為：AEFDHZMG

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

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

中序遍歷:       ADEFGHMZ

后序遍歷:       AEFDHZMG

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

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

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

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

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

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

2 在左子樹中遞歸。

3 在右子樹中遞歸。

4 打印當前根。

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

那么，前序遍歷:         GDAFEMHZ