C++中的樹、二叉樹、二叉樹周遊、二叉樹前序、中序、後序周遊互相求法

本博文來總結下樹、二叉樹以及二叉樹前序、中序、後序周遊互相求法，即如果知道兩個的周遊，如何求第三種周遊方法，比較笨的方法是畫出來二叉樹，然後根據各種周遊不同的特性來求，也可以程式設計求出，下面我們分别說明。

樹是一種資料結構，它是由n（n>=1）個有限結點組成一個具有層次關系的集合。

二叉樹是指結點的度不超過2的有序樹。

（結點的度：樹中的一個結點擁有的子樹數目。）

二叉樹前序周遊特性：

（1）、通路根節點 

（2）、前序周遊左子樹 

（3）、前序周遊右子樹 

二叉樹中序周遊特性： 

（1）、中序周遊左子樹 

（2）、通路根節點 

（3）、中序周遊右子樹 

二叉樹後序周遊特性：

（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。

第三步、觀察左子樹adef，左子樹的中的根節點必然是大樹的root的leftchild。在前序周遊中，大樹的root的leftchild位于root之後，是以左子樹的根節點為d。

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

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

1、 确定根，确定左子樹，确定右子樹。

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

那麼，前序周遊:         gdafemhz