網友af6bb57 2013-07-17

概念弄懂了，這個就懂了！

假設有棵樹，長下面這個樣子，它的前序遍歷，中序遍歷，後續遍歷都很容易知道。

前序：         GDAFEMHZ

中序：            ADEFGHMZ

後續：       AEFDHZMG

現在，假設僅僅知道前序和中序遍歷，如何求後序遍歷呢？比如，已知一棵樹的前序遍歷是”GDAFEMHZ”，而中序遍歷是”ADEFGHMZ”應該如何求後續遍歷？

第一步，root最簡單，前序遍歷的第一節點G就是root。

第二步，繼續觀察前序遍歷GDAFEMHZ，除了知道G是root，剩下的節點必然是root的左右子樹之外，沒法找到更多資訊了。

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

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

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

如何知道哪裡是前序遍歷中的左子樹和右子樹的分界線呢？透過中序遍歷去數節點的個數。

在上一次中序遍歷中，root左側是A、D、E、F，所以有4個節點位於root左側。那麼在前序遍歷中，必然是第1個是G，第2到第5個由A、D、E、F過程，第6個就是root的右子樹的根節點了，是M。

第六步，觀察發現，上面的過程是遞迴的。先找到當前樹的根節點，然後劃分為左子樹，右子樹，然後進入左子樹重複上面的過程，然後進入右子樹重複上面的過程。最後就可以還原一棵樹了。

第七步，其實，如果僅僅要求寫後續遍歷，甚至不要專門佔用空間儲存還原後的樹。只需要稍微改動第六步，就能實現要求。

時間問題：只能炒一些來答你：http：//blog。csdn。net/feliciafay/article/details/6816871

一路清晨503 2013-07-17

有大小順序的，左孩子比父節點和右孩子都大，比如一個前序遍歷5786342

5肯定是根節點了，7比5大那就是5的左孩子，8比7大就是7的左孩子，6比根節點5大比7小那就是7的右孩子，3比5小就是5的右孩子，4比根節點5小比3大就是3的左孩子，2比5小比3小就是3的右孩子

書架上的丫丫 2013-07-17

遞迴搜尋 ：前序：L M R 從根開始找。先找到L 子葉節點 ，在找M節點 ，對於R 節點遞迴找 L M R，就是3個元素不停遞迴知道沒有子節點···俺說不清了··第一個回答的好像不太對

1428409295 2013-07-17

前序遍歷DLR+中序遍歷LDR：末尾重複部分即為R，前序遍歷開頭字母為D，進而可推匯出L

其他同理

chr1999 2013-07-17

前L P R

中P L R

後R P L

P 父節點

L/R 左右節點