二叉樹先根序、後根序、中根序遍歷的速演算法（解題技巧）
經過研究我找出了一種不用畫圖，由先（後）根序遍歷和中根序遍歷迅速確定遍歷結果的辦法。謹以此文獻給智商與我同級而又不得不研究演算法的朋友。
抽象思維太差，用例子來說明吧。下面這個是後根遍歷的演算法。
例1：已知某二叉樹的先根序遍歷為abcdefg,中根序遍歷為cdbafeg，則它的後根序遍歷為_________
解法如下：
1、確定樹根。由先序遍歷知道，樹根為a。
2、分離左、右子樹。由中根序遍歷知，a左面的為cdb左子樹結點，右面的feg為右子樹結點。
把先根序遍歷也分成左、右子樹結點，bcd、efg。
前根序遍歷 bcdefg
中根序遍歷 cdbfeg
3、分別把先根序遍歷左、右子樹結點抄過來，寫的時候要從右往左寫，本例中，依次寫下b、c、d、，e、f、g，結果是dcb gfe。
當然不是簡單到這種程式。上面只是個原理。抄的過程應該是這樣的：
盯著前根序的，瞅著中根序的。如果要抄的先根序中的結點在中根序中是最左/右邊，則直接抄過來；如果不是，則把這個結點左邊的結點先放記在右根序的最左邊，然後繼續抄。本題的結果是dcb,fge,a, 即dcbfgea。
上面這個例子太短，看不出「貓膩」來。再舉個結點多一點兒的。
例2：已知某二叉樹的先根序遍歷為abcdefghijk,中根序遍歷為cedfbahkjig，則它的後根序遍歷為_________
按上面的方法：
前根序遍歷 bcdef ghijk
中根序遍歷 cedfb hkjig
依次抄得前根序的結點：f、e(e在中根序遍歷中不靠邊，所以先放在後根遍序曆中左子樹結點最左邊)、d、c
同理，把右子樹也抄過來。因此，寫下結點的過程依次是：
如果還是不太懂，你可以試著做一下下面的例子：
已知二叉樹前序遍歷 abcdefghijk，中序遍歷 cedfbahgkji，求後序遍歷。
解：(1)以根結點a分左、右子樹結點，
bcdef ghijk
cedfb hgkji
(2) 寫左子樹，盯著前序，從右到左開始寫
dcb （在中序中，b靠右邊，c靠左邊，d不靠邊。寫乙個，從中序中抹乙個。）
因為d在中序遍歷中不靠邊，所以下乙個結點e先擱到最左邊（注意，是「擱」，也就是說，不能把e從中序抹去。
e dcb
因為b已經抹了，f靠右邊。於是f仍然按照從右到左的規則，寫在d的的左邊。
e fdcb
最後把e加上，左子樹ok。
右子樹仍然從右到寫
g因為g不靠邊，所以下乙個結點h先擱在最左邊
h g然後繼續
h kjig
於是，結果是
efdcbhkjiga
前根序遍歷類似。
以上的方法只適用於三層以內的二叉樹（含三層）。在選擇題中，三層以上二叉樹也可用以上方法初步判斷正確答案。
二叉樹的遍歷
飛機票訂票系統 二 一四年六月 二叉數的遍歷 1 問題陳述 二叉樹的中序 前序 後序的遞迴 非遞迴遍歷演算法，層次序的非遞迴遍歷演算法的實現，應包含建樹的實現。限1 人完成 二叉樹的前序 後序的遞迴 非遞迴遍歷演算法，層次序的非遞迴遍歷演算法的實現，應包含建樹的實現。先序遍歷二叉樹演算法 若二叉樹為...
非遞迴遍歷二叉樹
遍歷二叉樹的非遞迴演算法 編寫的方法 根據樹中結點的遍歷規律及順序直接寫出其非遞迴演算法。先序非遞迴演算法 思路 假設 t是要遍歷樹的根指標，若t null 對於非遞迴演算法，引入棧模擬遞迴工作棧，初始時棧為空。問題 如何用棧來儲存資訊，使得在先序遍歷過左子樹後，能利用棧頂資訊獲取t的右子樹的根指標...
3最優二叉樹
計算機演算法的設計與分析實驗報告 1 描述 在權為wl，w2，wn的n個葉子所構成的所有二叉樹中，帶權路徑長度最小 即代價最小 的二叉樹稱為最優二叉樹或哈夫曼樹。例 給定4個葉子結點a，b，c和d，分別帶權7，5，2和4。構造如下圖所示的三棵二叉樹 還有許多棵 它們的帶權路徑長度分別為 a wpl ...