hce_kmu
113年
計算機概論與程式設計
第 12 題
Given a binary tree whose prefix order is ABCDEF and infix CBDAEF, what is its postfix order?
- A BCDFEA
- B CBDFEA
- C CDBFEA
- D CDBEFA
- E Undecided
思路引導 VIP
若我們知道一串序列總是從「整棵樹的最頂端」開始列出節點，而另一串序列則能清楚告訴我們哪些成員分佈在「某個節點」的左側或右側，你會如何結合這兩種資訊來定位每一位成員的正確位置呢？
🤖
AI 詳解
AI 專屬家教
恭喜你答對了！這代表你對二元樹（Binary Tree）的三種走訪順序（Traversal Order）有著非常清晰且正確的邏輯。要從前序（Prefix/Preorder）與中序（Infix/Inorder）推導出後序（Postfix），關鍵在於運用前序序列的第一個節點必為「根節點」的特性，並對照中序序列來區分出左、右子樹。
二元樹的結構還原與推導
首先，由前序 ABCDEF 可知 $A$ 為整棵樹的根節點。接著觀察中序 CBDAEF，以 $A$ 為中心可以將其餘成員切分為左子樹 ${C, B, D}$ 與右子樹 ${E, F}$。針對左子樹，前序序列顯示為 $B$ 為首（即子根），對應中序 $CBD$ 可知 $C$ 在左、$D$ 在右；而右子樹前序為 $EF$（$E$ 為子根），中序為 $EF$ 則顯示 $F$ 位於 $E$ 的右側。還原後的樹狀結構中，$A$ 的左邊連接 $B$（含小孩 $C, D$），右邊則是 $E$（含小孩 $F$）。最後，我們只要依照後序「左子樹 $\to$ 右子樹 $\to$ 根節點」的走訪規律，就能得出答案為 CDBFEA。
▼ 還有更多解析內容