moea_joint
114年
[資訊] 計算機原理、網路概論
第 8 題
給定一棵有 6 個節點的二元樹，前序走訪(Preorder)為 A,B,D,E,C,F，中序走訪(Inorder)為 D,B,E,A,C,F，其後序走訪(Postorder)為下列何者？
- A A,B,D,E,C,F
- B D,B,E,F,C,A
- C D,E,B,F,C,A
- D F,C,A,E,B,D
思路引導 VIP
想像你正在解開一個拼圖：如果「前序走訪」的第一個元素總是代表當前結構的「中心點（根節點）」，而「中序走訪」中這個中心點恰好會把左右兩邊的成員隔開，你會如何利用這兩個特性，像拆解套娃一樣，一步步抓出每一層的領導者與它的左右部屬呢？
🤖
AI 詳解
AI 專屬家教
恭喜你準確地判斷出正確答案！這顯示你對二元樹的走訪邏輯有非常紮實的理解。這類題目的核心在於靈活運用 前序 (Preorder) 掌握「根節點」的位置，並結合 中序 (Inorder) 區分出「左、右子樹」的成員範圍。
二元樹的還原與後序推導
在此題中，我們由前序的第一個元素得知 $A$ 為整棵樹的根，對照中序序列後，可以發現 ${D, B, E}$ 位於 $A$ 的左側，而 ${C, F}$ 位於右側。依此類推，在左子樹的成員中，前序序列顯示 $B$ 是最先出現的，因此 $B$ 是左子樹的根，且其左右分支分別為 $D$ 與 $E$。當結構完整還原後，再依照「左子樹 $\to$ 右子樹 $\to$ 根節點」的 後序 (Postorder) 規則：先處理最底層的 $D$ 與 $E$ 並回到 $B$，接著處理右側的 $F$ 與 $C$，最後才回到大根節點 $A$，即可得出正確序列。
▼ 還有更多解析內容