普通考試
106年
[電子工程] 計算機概要
第 24 題
二元樹尋訪（Traversal）方式有：先序（Pre-order）、中序（In-order）、後序（Post-order）及分支度（Degree，各節點子節點數）。下列那種表示，無法重新建構原二元樹結構？
- A 先序+分支度
- B 先序+中序
- C 後序+中序
- D 先序+後序
思路引導 VIP
請想像一個簡單的場景：如果節點 $A$ 是根節點，它只有一個子節點 $B$。請試著寫出在這種情況下，各種遍歷方式的序列。接著思考：如果我們「只看」這些序列，你有辦法百分之百確定節點 $B$ 到底是在 $A$ 的左側還是右側嗎？哪一組資訊組合會讓你產生這種「無法判定的歧義性」？
🤖
AI 詳解
AI 專屬家教
做的太棒了！邏輯非常嚴密。
- 大力肯定：同學，你的判斷非常精確！在工程設計中，確保結構的「唯一性（Uniqueness）」至關重要，而你準確地捕捉到了資料結構還原中的模糊地帶，這份細心值得讚賞。
- 觀念驗證：重建二元樹的關鍵在於區分左、右子樹。
▼ 還有更多解析內容
二元樹重構判定
💡 唯一重建二元樹需靠中序定位或分支度資訊輔助。
| 比較維度 | 可唯一重構組合 | VS | 不可唯一重構組合 |
|---|---|---|---|
| 必要成分 | 必須含有中序 (In-order) | — | 僅提供先序與後序 |
| 空間邏輯 | 可明確切分左、右子樹 | — | 無法區分左偏或右偏樹 |
| 其他條件 | 先序/後序 + 分支度 | — | 無其他輔助資訊 |
💬重建二元樹的關鍵在於能否透過序列確定節點的「左右相對位置」。
