調查局三等申論題
112年
[電子科學組] 計算機概論
第 二 題
📖 題組：
五、T 為一二元樹（Binary Tree），可以是空的或是每一個節點儲存著一個數值且與其他節點的數值不重複。假設 T 起始為空的，即 T = null。樹中節點（node）的定義如下： struct node{ int data; struct node *l_link, *r_link; } 請回答下列問題：
五、T 為一二元樹（Binary Tree），可以是空的或是每一個節點儲存著一個數值且與其他節點的數值不重複。假設 T 起始為空的，即 T = null。樹中節點（node）的定義如下： struct node{ int data; struct node *l_link, *r_link; } 請回答下列問題：
📝 此題為申論題，共 4 小題
小題 (二)
請設計一演算法以在樹中搜尋一給定鍵值（key），如：Search（T, key）。若 key 存在 T 中，回傳“found”；若 key 不存在 T 中，回傳“not found”。（10 分）
思路引導 VIP
看到題目說明為一般「二元樹」而非「二元搜尋樹（BST）」，第一時間要警覺不能使用數值大小進行左右分枝的二分搜尋。必須採用圖形走訪演算法（如深度優先搜尋 DFS），利用遞迴方式遍歷每個節點，直到比對成功或走訪完整棵樹為止。
小題 (一)
插入一節點其 data 欄位為 value 的演算法如下：
Procedure Insert(T, value)
Begin
If(T == null)
建立一個新節點，並將data欄位設為value;
Elseif(T->data > value)
Insert(T->l_link, value);
Else
Insert(T->r_link, value);
Endif
End
請根據以上插入節點的演算法依序插入節點，其值分別為：23，56，12，19，42，4，98，36。請以圖示的方式呈現完整的插入過程。（10 分）
Procedure Insert(T, value)
Begin
If(T == null)
建立一個新節點，並將data欄位設為value;
Elseif(T->data > value)
Insert(T->l_link, value);
Else
Insert(T->r_link, value);
Endif
End
請根據以上插入節點的演算法依序插入節點，其值分別為：23，56，12，19，42，4，98，36。請以圖示的方式呈現完整的插入過程。（10 分）
思路引導 VIP
本題測驗二元搜尋樹（Binary Search Tree, BST）的建構過程。根據提供的演算法，插入規則為：「欲插入值小於目前節點值則往左子樹走，大於則往右子樹走」，依序讀取數列並畫出每一階段的樹狀結構即可得分。
小題 (三)
若 T 中有 n 個節點。最糟的情況下，需要搜尋幾次？（5 分）
思路引導 VIP
考生應聯想到二元樹在沒有平衡機制（如 AVL Tree）的情況下，其最糟結構為「歪斜二元樹（Skewed Binary Tree）」。此時樹的深度與節點數相等，搜尋過程等同於走訪單向鏈結串列。
小題 (四)
承第(三)子題，此最糟的情況是什麼？請舉例說明。（5 分）
思路引導 VIP
看到二元搜尋樹的『最糟情況』，應立刻聯想到『樹的退化』。請思考當輸入資料已經呈現規則排序（遞增或遞減）時，樹的結構會變成一邊倒的『歪斜樹（Skewed Tree）』，導致時間複雜度從 O(log n) 退化為 O(n)。