普考-資訊處理計算機概要111 年第 27 題單選題
使用下列數字序列：20、2、3、4、7、6、9、1、5、8，依序輸入建立一個二元搜尋樹（binary search tree），下列敘述何者錯誤？
A由根節點出發使用前序（preorder）方式走訪此二元搜尋樹，輸出為 20, 2, 1, 3, 4, 7, 6, 5, 9, 8
B節點 1 和節點 3 的父節點相同
C節點 6 位於節點 9 的左子樹正確答案
D若最後再新增一個數字 10，此二元搜尋樹的高度不變
C正確答案
BST 依序插入後，節點 6 是節點 7 的左子，節點 9 是節點 7 的右子；6 與 9 互為兄弟節點的子孫關係需看清楚。
為什麼答案是 C
插入順序 7→6→9：6 比 7 小放左，9 比 7 大放右。所以 6 與 9 為兄弟節點，6 並不在 9 的左子樹中，敘述錯誤，為正解。
載入中…
完整詳解
Pro · 無限重點 BST 依序插入後，節點 6 是節點 7 的左子，節點 9 是節點 7 的右子；6 與 9 互為兄弟節點的子孫關係需看清楚。
畫出 BST 樹狀圖：20 為根，2 在左，其餘依 BST 規則放置，再逐一驗證選項。
逐選項分析
A✕
前序走訪為 根→左→右。依建樹結果：20→2→1、2→3→4→7→6→5、7→9→8，輸出 20,2,1,3,4,7,6,5,9,8 正確。
B✕
插入 2 後，1 走到 2 的左子，3 走到 2 的右子，兩者父節點皆為 2，敘述正確。
C✓ 正確
插入順序 7→6→9：6 比 7 小放左，9 比 7 大放右。所以 6 與 9 為兄弟節點，6 並不在 9 的左子樹中，敘述錯誤，為正解。
D✕
原樹最深路徑為 20→2→3→4→7→6→5 或 20→2→3→4→7→9→8，均為第 7 層（若高度以邊數計為 6）。新增 10 時：10<20 往左，再大於 2、3、4、7、9；8 是 9 的左子，9 的右子為空，故 10 成為 9 的右子，仍為第 7 層，高度不變，敘述正確。
BST 建樹過程（20,2,3,4,7,6,9,1,5,8）
| 插入值 | 路徑 | 放置位置 | 父節點 |
|---|
| 20 | — | 根 | 無 |
| 2 | 20→左 | 20 的左子 | 20 |
| 3 | 20→2→右 | 2 的右子 | 2 |
| 4 | 20→2→3→右 | 3 的右子 | 3 |
| 7 | 20→2→3→4→右 | 4 的右子 | 4 |
| 6 | 20→2→3→4→7→左 | 7 的左子 | 7 |
| 9 | 20→2→3→4→7→右 | 7 的右子 | 7 |
| 1 | 20→2→左 | 2 的左子 | 2 |
| 5 | 20→2→3→4→7→6→左 | 6 的左子 | 6 |
| 8 | 20→2→3→4→7→9→左 | 9 的左子 | 9 |
C 選項是陷阱：6 和 9 都是 7 的直接子節點（兄弟關係），6 並不在 9 的左子樹裡。考生若沒畫樹圖，容易誤以為 6<9 所以 6 在 9 的左子樹，這是混淆「BST 大小關係」和「實際樹結構」。 
