高考申論題
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){
// 考生需在此處撰寫遞迴程式
}
📝 此題為申論題
思路引導 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）」與排序的關聯性。 【理論/法規依據】
▼ 還有更多解析內容