資料結構-樹-已經知道先根（後根）和中根 建構樹（轉載）

已知二叉樹的先/後根序周遊和中根序周遊可唯一确定一棵二叉樹，資料結構試題中常有已知先(後)根序周遊要求确定後（先）根序周遊題型。一般的，我們要按照已知的條件把二叉樹畫出來，再按圖寫出結果。這樣麻煩的事常讓我感到混亂而不得不出錯。經過研究我找出了一種不用畫圖，由先（後）根序周遊和中根序周遊迅速确定周遊結果的辦法。謹以此文獻給智商與我同級而又不得不研究算法的朋友。

抽象思維太差，用例子來說明吧。下面這個是後根周遊的算法。

例1：已知某二叉樹的先根序周遊為ABCDEFG,中根序周遊為CDBAFEG，則它的後根序周遊為

解法如下：

1、确定樹根。由先序周遊知道，樹根為A。

2、分離左、右子樹。由中根序周遊知，A左面的為CDB左子樹結點，右面的FEG為右子樹結點。

把先根序周遊也分成左、右子樹結點，BCD、EFG。

　　　　　　前根序周遊　BCD EFG

中根序周遊　CDB FEG

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　

前根序周遊類似。

以上的方法隻适用于三層以内的二叉樹（含三層）。在選擇題中，三層以上二叉樹也可用以上方法初步判斷正确答案。

範晨鵬

軟體是一種态度

成功是一種習慣