高考申論題
111年
[資訊處理] 資料結構
第 三 題
一個二元搜尋樹（Binary search tree）的前序追蹤（Preorder traversal）結果如下：14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20
請建構此二元搜尋樹。接著利用如下 C 語言對二元樹節點的宣告，使用 C 語言寫一遞迴程式 sortTree（NODEPTR tree），輸入二元樹的根節點，來處理此二元樹的節點資料，並將資料依由小至大輸出。（25 分）
struct node{
int info;
struct node *left;
struct node *right;
}
typedef struct node *NODEPTR;
void sortTree(NODEPTR tree){
// 考生需在此處撰寫遞迴程式
}
請建構此二元搜尋樹。接著利用如下 C 語言對二元樹節點的宣告，使用 C 語言寫一遞迴程式 sortTree（NODEPTR tree），輸入二元樹的根節點，來處理此二元樹的節點資料，並將資料依由小至大輸出。（25 分）
struct node{
int info;
struct node *left;
struct node *right;
}
typedef struct node *NODEPTR;
void sortTree(NODEPTR tree){
// 考生需在此處撰寫遞迴程式
}
📝 此題為申論題
思路引導 VIP
本題包含兩個任務：重建 BST 與實作排序輸出。
- 建構 BST：二元搜尋樹的特性是「左小右大」。給定前序（Root, Left, Right），第一個元素 14 必為 Root。接下來比 14 小的序列（4, 3, 9, 7, 5）構成左子樹，比 14 大的（15, 18, 16, 17, 20）構成右子樹。依此規則遞迴推導即可畫出圖形。
🤖
AI 詳解
AI 專屬家教
【考點分析】 本題考察「二元搜尋樹（BST）」的重建邏輯以及「中序追蹤（Inorder Traversal）」與排序的關聯性。 【理論/法規依據】
▼ 還有更多解析內容
BST 建構與排序走訪
💡 掌握 BST 性質重建結構，並透過中序追蹤達成升序排序輸出。
🔗 二元搜尋樹排序處理流程
- 1 前序建樹 — 首位為根，其後依大小分配至左、右子樹。
- 2 中序走訪 — 進入遞迴，依「左、根、右」順序處理節點。
- 3 節點輸出 — 中序存取點正好符合資料由小到大的順序。
- 4 升序結果 — 遞迴結束後即可獲得完整的排序序列。
↓
↓
↓
🔄 延伸學習：延伸學習：當 BST 嚴重傾斜時，搜尋效率會從 O(log n) 退化至 O(n)。
