109 年 國立臺灣大學生物機電系碩士班丙組《資料結構（C）》

核心觀念

二元堆（binary heap）必須同時符合：

1. 完全二元樹形狀：除最後一層外皆填滿，最後一層由左至右排列。
2. 堆序性質：
   • Max-heap：每個父節點皆大於等於子節點。
   • Min-heap：每個父節點皆小於等於子節點。

若使用陣列儲存，採用 1-based index 時：

$$\text{left}(i)=2i,\qquad \text{right}(i)=2i+1,\qquad \text{parent}(i)=\left\lfloor\frac{i}{2}\right\rfloor$$

題目要求在 $O(N)$ 時間內建立二元堆。逐一插入每個元素需 $O(\log N)$，總時間為 $O(N\log N)$，不符合要求。因此應採用 Bottom-up heap construction，由最底層的內部節點向上執行 sift-down。

---

解題方法

以建立 Max-heap 為例。陣列中索引大於 $\lfloor N/2\rfloor$ 的節點都是葉節點，葉節點本身已經是合法的堆。因此只需處理索引：

$$\left\lfloor\frac{N}{2}\right\rfloor,\ \left\lfloor\frac{N}{2}\right\rfloor-1,\ \ldots,\ 1$$

對每個內部節點執行 sift-down：

1. 比較目前節點與左右子節點。
2. 找出三者中最大的元素。
3. 若目前節點已經是最大值，停止。
4. 若子節點較大，交換目前節點與較大的子節點。
5. 繼續向下修正交換後的位置。

關鍵伪程式如下：

BuildMaxHeap(A, N):
    for i = floor(N / 2) downto 1:
        SiftDown(A, i, N)

SiftDown(A, i, N):
    while 2i <= N:
        left  = 2i
        right = 2i + 1
        largest = i

        if left <= N and A[left] > A[largest]:
            largest = left

        if right <= N and A[right] > A[largest]:
            largest = right

        if largest == i:
            break

        swap(A[i], A[largest])
        i = largest

建立 Min-heap 時，只需將比較條件中的「較大」改為「較小」。

---

正確性證明

以 Max-heap 為例，證明 BuildMaxHeap 結束後，整個陣列必定代表合法的 Max-heap。

對外層迴圈建立以下不變量：

當處理索引 $i$ 時，所有索引大於 $i$ 的節點，其子樹皆已經是合法的 Max-heap。

初始情況

核心觀念

題目要求資料結構同時支援三種操作：

• push(x)：將元素 $x$ 放入堆疊頂端。
• pop()：移除並回傳堆疊頂端元素。
• getMin()：回傳目前堆疊中的最小值。

一般堆疊可在 $O(1)$ 時間完成 push 與 pop，但若每次執行 getMin() 都掃描全部元素，最差需要 $O(n)$ 時間。

關鍵是：除了保存每個元素本身，也同步保存「截至目前為止的最小值」。如此即可在堆疊頂端直接取得全體元素的最小值。

---

解題方法：使用附帶最小值的堆疊

令每個堆疊節點儲存一組資料：

$$(value,\ currentMin)$$

其中：

• value 是該節點實際儲存的元素。
• currentMin 是從堆疊底部到該節點為止的最小值。

假設原本堆疊頂端的最小值為 $m$，插入新元素 $x$ 後，新頂端的最小值為：

$$\min(x,m)$$

因此每次 push 時，只需將新元素與舊的最小值比較。

操作定義

push(x)

若堆疊為空：

$$currentMin=x$$

若堆疊不為空：

$$currentMin=\min(x,\ top.currentMin)$$

再將 $(x,currentMin)$ 放入堆疊頂端。

pop()

直接移除堆疊頂端節點，並回傳其中的 value。

移除後的新堆疊頂端已經保存正確的最小值，因此不需要重新掃描。

getMin()

直接回傳堆疊頂端節點的 currentMin。

---

範例

依序執行：

$$push(5),\ push(3),\ push(7),\ push(2)$$

堆疊內容如下：

元素 value	currentMin
$5$	$5$
$3$	$3$
$7$	$3$
$2$	$2$

此時：

$$getMin()=2$$

執行 pop() 移除 $2$ 後，新的堆疊頂端為 $(7,3)$，因此：

$$getMin()=3$$

執行 pop() 移除 $7$ 後，最小值仍由節點 $(3,3)$ 保存：

$$getMin()=3$$

整個過程不需要掃描堆疊。

---

C 語言實作

核心觀念

二元搜尋樹（Binary Search Tree, BST）的定義是：

• 每個節點左子樹的所有鍵值都小於該節點鍵值。
• 每個節點右子樹的所有鍵值都大於該節點鍵值。
• 左、右子樹本身也必須是 BST。

本題未指定重複鍵值的處理方式，以下採用最常見的嚴格定義：

$$\text{左子樹鍵值}<\text{節點鍵值}<\text{右子樹鍵值}$$

只檢查「每個節點和自己的左右子節點」是不充分的，因為錯誤可能出現在更深層的子孫。例如：

    10
   /  \
  5    15
      /
     7

節點 $7$ 雖然小於父節點 $15$，但它位於 $10$ 的右子樹中，應大於 $10$，因此整棵樹不是 BST。

正確方法是對每個節點維護其允許的鍵值範圍。

解題方法：遞迴維護上下界

根節點一開始可以接受所有鍵值，因此其合法範圍為：

$$(-\infty,+\infty)$$

若目前節點的鍵值為 $x$，且目前合法範圍為 $(low, high)$，則必須滿足：

$$low < x < high$$

接著更新子樹範圍：

• 左子樹所有鍵值必須介於 $low$ 與 $x$ 之間。
• 右子樹所有鍵值必須介於 $x$ 與 $high$ 之間。

因此：

$$\text{左子樹範圍}=(low,x)$$ $$\text{右子樹範圍}=(x,high)$$

偽程式碼

function IsBST(root):
    return Check(root, -infinity, +infinity)


function Check(node, low, high):
    if node == NULL:
        return true

    if node.key <= low or node.key >= high:
        return false

    return Check(node.left, low, node.key)
           and Check(node.right, node.key, high)

若鍵值型別不支援 $-\infty$ 與 $+\infty$，可在實作中使用「尚未設定上下界」的標記，或選用保證超出所有合法鍵值的邊界值。

正確性說明

核心觀念

本題考查二元搜尋樹（Binary Search Tree, BST）的刪除操作。

BST 必須符合以下性質：

• 任一節點左子樹的所有鍵值皆小於該節點鍵值。
• 任一節點右子樹的所有鍵值皆大於該節點鍵值。
• 對每一個子樹也都成立相同規則。

刪除節點後，樹仍須維持 BST 性質。依被刪除節點的子女數量，分成三種情況：

1. 沒有子女：直接刪除該節點。
2. 只有一個子女：由唯一子女接替該節點的位置。
3. 有兩個子女：以其中序後繼接替該節點，再刪除原本的後繼節點。

其中序後繼是「右子樹中的最小節點」，其鍵值大於目前節點，且是所有大於目前鍵值的節點中最小者，因此可安全維持 BST 性質。

---

解題方法

函式必須從根節點開始搜尋輸入的 key：

• 若 key < root.key，應到左子樹刪除。
• 若 key > root.key，應到右子樹刪除。
• 若 key == root.key，代表找到待刪除節點，依子女數量處理。

遞迴函式必須回傳「刪除後的子樹根節點」，因為刪除節點時，父節點的 left 或 right 指標可能需要重新連接。

偽程式碼

function deleteKey(root, key):
    if root == NULL:
        return NULL

    if key < root.key:
        root.left = deleteKey(root.left, key)
        return root

    if key > root.key:
        root.right = deleteKey(root.right, key)
        return root

    // 此處表示 root.key == key，已找到待刪除節點

    // 情況一：沒有左子女
    if root.left == NULL:
        return root.right

    // 情況二：沒有右子女
    if root.right == NULL:
        return root.left

    // 情況三：同時具有左右子女
    successor = findMinimum(root.right)

    root.key = successor.key
    root.right = deleteKey(root.right, successor.key)

    return root


function findMinimum(root):
    current = root

    while current.left != NULL:
        current = current.left

    return current

---

三種刪除情況說明

情況一：葉節點

若待刪除節點沒有左、右子女：

root.left == NULL
root.right == NULL

此時函式會符合：

if root.left == NULL:
    return root.right

因為 root.right 也是 NULL，所以父節點接回 NULL，該葉節點便從樹中移除。

---

情況二：只有一個子女

若節點只有右子女：

核心觀念

本題考查「中序表示式（infix expression）轉後序表示式（postfix expression）」的方法，核心資料結構是堆疊（stack）。

• 中序：運算子位於兩個運算元之間，例如 $A+B$
• 後序：運算子位於兩個運算元之後，例如 $AB+$
• 後序表示式不需要括號，運算順序由運算子的排列直接決定。

轉換時遵守：

1. 整數直接輸出。
2. 左括號 ( 直接推入堆疊。
3. 右括號 ) 讓堆疊中的運算子持續彈出並輸出，直到遇到左括號；左括號彈出後丟棄。
4. 遇到運算子時，先彈出堆疊頂端優先權較高或相同的運算子，再將目前運算子推入堆疊。
5. 輸入結束後，將堆疊內剩餘運算子全部彈出。

本題假設整數與運算子之間以單一空白分隔，因此可以逐一讀取 token，不需額外處理多位數字的切割問題。

運算子優先權

以常見的四則運算為例：

$$\operatorname{prec}(+) = \operatorname{prec}(-) = 1$$ $$\operatorname{prec}(*) = \operatorname{prec}(/) = 2$$

括號只用來控制運算順序，本身不輸出到後序表示式。

解題方法

使用一個運算子堆疊 S，並使用輸出序列 P 儲存後序結果。

遇到運算子 $op$ 時，若堆疊頂端是運算子 $top$，且滿足：

$$\operatorname{prec}(top) \geq \operatorname{prec}(op)$$

則先將 $top$ 彈出並加入輸出序列，再把 $op$ 推入堆疊。這樣可以確保優先權較高的運算先輸出；相同優先權的運算子也能維持左結合的計算順序。

虛擬碼

procedure InfixToPostfix(tokens):
    create empty stack S
    create empty output list P

    for each token t in tokens:
        if t is an integer:
            append t to P

        else if t == "(":
            push t into S

        else if t == ")":
            while S is not empty and top(S) != "(":
                append pop(S) to P

            if S is not empty and top(S) == "(":
                pop(S)

        else if t is an operator:
            while S is not empty
                  and top(S) != "("
                  and precedence(top(S)) >= precedence(t):
                append pop(S) to P

            push t into S

    while S is not empty:
        if top(S) == "(":
            report mismatched parentheses
        else:
            append pop(S) to P

    return P

逐步轉換

輸入：

( 5 * ( ( 9 * 8 ) + ( 7 * ( 4 + 6 ) ) ) )