Q42.
某二元樹(Binary Tree)之中序走訪(Inorder Traversal)為ABCDEFGHJK，後序走訪(Postorder Traversal)為ACEDBJHKGF，對於該二元樹之性質，下列敘述何者是正確？
電腦軟體設計共同科目 · 乙級 · Q42
難易度分析
4 / 5
此題目要求考生在已知兩種走訪序列的情況下，必須先重建完整的二元樹結構，再推導出第三種走訪結果。由於重建過程涉及多次遞迴分析，且選項間的字母排列高度相似，需要極高的精確度才能區分正確答案，因此判定為較高難度。
正確答案：③前序走訪為FBADCEGKHJ
③ 前序走訪為FBADCEGKHJ:此為正確的前序走訪序列。由後序走訪最後一個元素 F 為根節點，配合中序走訪劃分左右子樹，依序遞迴重建二元樹後，執行根-左-右的前序走訪即得 FBADCEGKHJ。
錯誤選項解析
- ① 前序走訪(Preorder Traversal)為FBADCEKGHJ:此前序走訪序列中 KGHJ 的順序錯誤。正確應為 GKHJ，因為 G 是 F 的右子節點，應先於 K 被走訪。
- ② 前序走訪為FBACDEGKHJ:此序列中 ACDE 的順序錯誤。正確應為 ADCE，因為 D 是 B 的右子節點，在前序走訪中應於 C 和 E 之前被訪問。
- ④ 前序走訪為FBADECGKHJ:此序列中 DEC 的順序錯誤。正確應為 DCE，因為 C 是 D 的左子節點，在前序走訪中應先於 E（D 的右子節點）被訪問。
Learning Tip
"此類題型的核心考點在於利用中序走訪與後序走訪（或前序走訪）唯一重建二元樹。關鍵步驟為：後序的最後一個元素必為根節點，再以此根節點在中序序列中劃分左子樹與右子樹的範圍，遞迴重建整棵樹後即可推導出第三種走訪序列。常見陷阱是混淆前序（根左右）、中序（左根右）、後序（左右根）的訪問順序，建議在草稿紙上實際畫出樹狀結構以避免出錯。"
學員答題分佈
①前序走訪(Preorder Traversal)為FBADCEKGHJ0%
②前序走訪為FBACDEGKHJ0%
③前序走訪為FBADCEGKHJ0%
④前序走訪為FBADECGKHJ0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！
相似類型題目
已知某個二元樹(Binary Tree) 之中序(Inorder) 為DCEBAFHGJIK ，而後序(Postorder)為DECBHJKIGFA，下列敘述那些是正確？
某二元樹(Binary Tree)之中序走訪(Inorder Traversal)為ABCDEFGHJK，後序走訪(Postorder Traversal)為ACEDBJHKGF，對於該二元樹之性質，下列敘述何者是正確？
某二元樹(Binary Tree)之中序走訪(Inorder Traversal)為EFGBHCDATRS，而後序走訪(Postorder Traversal)為GFEHDCBTSRA，對於該二元樹之性質，下列敘述何者是正確的？
某二元樹(Binary Tree)之中序走訪(Inorder Traversal)為ABCDEFGHJK，後序走訪(Postorder Traversal)為ACEDBJHKGF，對於該二元樹之性質，下列敘述何者是正確？
某二元樹(Binary Tree)之中序走訪(Inorder Traversal)為ABCDEFGHJK，後序走訪(Postorder Traversal)為ACEDBJHKGF，對於該二元樹之性質，下列敘述何者是正確？