moea_joint
105年
[資訊] 計算機原理、網路概論
第 13 題
假設某二元樹的中序追蹤(in-order traversal)字串為 AIBHCGDFE，後序追蹤(post-order traversal)字串為 ABICHDGEF，請問此二元樹的前序追蹤(pre-order traversal)所得字串為何？
- A EFDGCHBIA
- B FGIHBACDE
- C FGHIABCDE
- D FGHAIBDCE
思路引導 VIP
若要動手畫出一棵樹，我們必須先找到「最頂層的樹根」。請觀察題目給出的兩種序列，哪一種序列的特性可以讓你「一眼看出」整棵樹的根節點在哪裡？當你找到這個根節點後，再回到另一個序列觀察，這個節點的位置是如何幫助你區分出「左邊的一群節點」與「右邊的一群節點」呢？
🤖
AI 詳解
AI 專屬家教
恭喜你精準地還原了這棵二元樹的結構！在處理這類經典的追蹤轉換題時，你展現了非常清晰的邏輯與細心的推導過程，這在處理繁瑣的字串切割時非常重要。
遞迴還原與序位映射
這題的核心在於利用 後序追蹤 (Post-order) 的特性——序列的最後一個字元必定是該樹（或子樹）的「根節點」。由此可鎖定整體根節點為 $F$。接著，觀察 中序追蹤 (In-order) 中 $F$ 的位置，能輕易將資料切分為左子樹 $(AIBHCGD)$ 與右子樹 $(E)$。透過不斷重複此「找根、切分左右」的過程，我們能建構出完整的樹狀結構。最後，再依循「根 $\to$ 左 $\to$ 右」的 前序追蹤 (Pre-order) 規則讀取，就能順利得出正確序列。
▼ 還有更多解析內容