身心障礙人員考試身障四等-資訊處理類科計算機概要105 年第 15 題單選題
一個二元樹（binary tree），使用中序走訪（inorder traversal）的結果為：A E G H D F B C ；使用後序走訪（postorder traversal）的結果為：A H F D G B C E。請問節點 B 的左兒子（left child）為何？
D正確答案
後序最後是根 E，切中序左右子樹，遞迴重建即可得 B 的左子為 G。
為什麼答案是 D
B 子樹中序 GHDFB、後序 HFDGB，後序末為 B，其前一個 G 為 B 左子樹之根，即 B 的左兒子。
載入中…
完整詳解
Pro · 無限重點 後序最後是根 E，切中序左右子樹，遞迴重建即可得 B 的左子為 G。
後序末位=根，用中序切左右；對 B 子樹中序為 GHDFB、後序為 HFDGB → B 左子=G。
逐選項分析
A✕ 陷阱
D 在中序 GHDF 中位於 G 的右子樹內，是 G 的右子孫，不是 B 的直接左兒子。
B✕
E 是整棵樹的根（後序最後一個），是 B 的祖先而非兒子。
C✕ 陷阱
F 在 G 的右子樹中，為 D 的右兒子，並非 B 的直接左兒子。
D✓ 正確
B 子樹中序 GHDFB、後序 HFDGB，後序末為 B，其前一個 G 為 B 左子樹之根，即 B 的左兒子。
由中序+後序重建二元樹步驟
| 步驟 | 動作 | 本題套用 | 結果 |
|---|
| 1 | 後序最後一個=根 | postorder 末=E | 根=E |
| 2 | 中序中根左=左子樹 | AEGHDF|B C 中 E 左為 A | E 左子樹={A} |
| 3 | 中序中根右=右子樹 | E 右為 GHDFBC | E 右子樹根=C(後序末) |
| 4 | 遞迴右子樹 | 中序 GHDFB、後序 HFDGB→根 B | B 左子樹={G,H,D,F} |
| 5 | B 左子樹找根 | 後序 HFDG 末為 G | B 左兒子=G |
