中序為ECFBDAHG
後序為EFBCHGAD
後序最後一個元素一定是根,也就是 D 是根
D
接下來看中序
D 把中序一分為二,左半部 ECFB 右半部 AHG
左半部 = 左半邊的節點
右半部 = 右半邊的節點
=====================================
先從左半部開始看
中序為ECFB
後序為EFBC(去掉 D 及右半部的元素)
後序最後一個元素為 C,代表左半部的根是 C
D
/
C
C 把中序一分為二,左半部 E 右半部 FB
因為左半部只剩下一個元素,直接畫上去
D
/
C
/
E
剩下的元素為右半部的 FB
中序為FB
後序為FB(去掉 C 及 E)
後序最後一個元素為 B,代表右半部的根是 B
D
/
C
/ \
E B
剩下一個 F 在 B 的左邊,直接畫上去
D
/
C
/ \
E B
/
F
=====================================
剩下右半的節點,步驟都一樣
中序為AHG
後序為HGA
後序最後一個元素為 A,代表右半部的根是 A
D
/ \
C A
/ \
E B
/
F
剩下的元素為右半部的 HG
中序為HG
後序為HG(去掉 A)
後序最後一個元素為 G,代表右半部的根是 G
D
/ \
C A
/ \ \
E B G
/
F
剩下一個 H 在 G 的左邊,直接畫上去
D
/ \
C A
/ \ \
E B G
/ /
F H
如果還是不會就放棄這一類型的題目吧
首先,不知道你知不知道前中後序走訪是如何去運行的,不知道的話你可以看這篇。
前輩已經有作出解釋了。
https://ithelp.ithome.com.tw/articles/10205571
接下來看題目給的條件,他已有說
中序為ECFBDAHG
後序為EFBCHGAD
可知root為D(後序尾),右有AHG,左有ECFB(中序透過root左右區分)
最左下為E,那接下來就是CFB這三個東西要做排列,這邊建議開始進行繪圖去判斷,當然你必須先理解中序跟後序的遍歷流程,那理論上圖會畫出來長這樣
空空D
空C
空空B
空F
E
右邊我不管,反正答案就出來了。
答案是 D
10年前就有人回答了
最新此題出處
110年一次考上銀行 計算機概論(含網路概論)
題目在第 140 頁 第5題
答案在第 142 頁,答案是D。此二元樹的前序追蹤為 DCEBFAHG
不服去找出版社辯