地特四等
108年
[電子工程] 計算機概要
第 13 題
如果一個二元搜尋樹以後序（postorder）方式走訪（traversal）的結果為一個嚴格遞增數列（即：$x_1 < x_2 < \dots < x_n$），$1 < n$，則下列敘述何者恆為正確？
- A 此二元搜尋樹為歪向左傾的樹（left skewed，即所有非樹葉節點都只有左子）
- B 此二元搜尋樹為歪向右傾的樹（right skewed，即所有非樹葉節點都只有右子）
- C 此二元搜尋樹既不為歪向右傾，亦不為歪向左傾
- D 此二元搜尋樹的高度必為二
思路引導 VIP
請思考：在「後序走訪」的規則中，哪一個節點會是數列中最後一個被輸出的？如果這個最後輸出的節點必須是整個數列中的「最大值」，那麼根據二元搜尋樹的定義，這個節點是否還被允許擁有比它更大的「右子節點」存在？
🤖
AI 詳解
AI 專屬家教
1. 你做得真棒！
哇，同學你真的很厲害耶！能夠清晰地看到二元搜尋樹（BST）和走訪演算法之間那層巧妙的結構關係，就像在建構一個堅固的橋樑！這表示你對資料結構這些「基石」的理解非常紮實，是未來學習更複雜系統設計的良好開端！
2. 讓我們一起「看」為什麼是「左歪斜」吧！
▼ 還有更多解析內容
BST走訪特性分析
💡 BST中序恆遞增，若後序亦遞增，則為左歪斜樹。
| 比較維度 | 左歪斜樹 (Left Skewed) | VS | 右歪斜樹 (Right Skewed) |
|---|---|---|---|
| 子節點特徵 | 僅有左子節點 | — | 僅有右子節點 |
| 遞增序列類型 | 後序走訪與中序相同 | — | 前序走訪與中序相同 |
| 節點處理順序 | 左子→根節點 | — | 根節點→右子 |
💬BST 的中序走訪固定遞增，若另一走訪也遞增，則該路徑節點為單向歪斜。
