111 年 國立中山大學電機工程學系碩士班丙組《資料結構》

核心觀念

• 二元搜尋樹（BST）：每個節點的左子樹鍵值小於該節點，右子樹鍵值大於該節點。新值從根節點開始比較，直到找到空位置插入。
• 最小堆積（min-heap）：必須是完全二元樹，且每個父節點的值都小於或等於子節點。新值先放在下一個可用位置，再沿父節點方向向上調整。
• AVL 樹：每個節點左右子樹高度差的絕對值不得大於 $1$。若插入後失衡，依失衡型態進行旋轉。

解題方法

依序插入 $60、35、11、45、8、72、6$。以下每個步驟都畫出新增一個整數後的樹。

① 二元搜尋樹

依大小比較決定插入位置，不進行旋轉。

插入 $60$

60

插入 $35$

  60
 /
35

插入 $11$

    60
   /
  35
 /
11

插入 $45$

    60
   /
  35
 /  \
11  45

插入 $8$

      60
     /
    35
   /  \
  11  45
 /
8

插入 $72$

      60
     /  \
    35  72
   /  \
  11  45
 /
8

插入 $6$

        60
       /  \
      35  72
     /  \
    11  45
   /
  8
 /
6

② 最小堆積

新值先放在完全二元樹的下一個空位，再與父節點比較；若新值較小，就交換並繼續向上調整。

插入 $60$

60

插入 $35$：$35<60$，與父節點交換。

  35
 /
60

插入 $11$：$11<35$，與父節點交換。

   11
  /  \
60   35

插入 $45$：$45<60$，與父節點交換。

    11
   /  \
  45  35
 /
60

插入 $8$：依序與 $45、11$ 交換。

     8
   /   \
 11    35
 / \
60 45

核心觀念

Min-heap 必須符合兩個條件：完全二元樹的形狀，以及每個父節點的鍵值都小於或等於子節點。刪除最小值時，以最後一個節點補到根，再沿著較小的子節點向下調整。

AVL 樹是高度平衡的二元搜尋樹。每個節點的左右子樹高度差絕對值不得超過 $1$。刪除有兩個子節點的節點時，以下採用常見作法：以其中序後繼取代，再刪除原後繼節點。

解題方法

依第 1 題給定的輸入順序 $60,35,11,45,8,72,6$，逐一插入兩種樹。

① Min-heap 刪除 $6$

逐一插入並維持 min-heap，陣列表示如下：

插入值	Heap 陣列
$60$	$[60]$
$35$	$[35,60]$
$11$	$[11,60,35]$
$45$	$[11,45,35,60]$
$8$	$[8,11,35,60,45]$
$72$	$[8,11,35,60,45,72]$
$6$	$[6,11,8,60,45,72,35]$

刪除根節點 $6$，以最後一個值 $35$ 補到根：

$$[35,11,8,60,45,72]$$

根的兩個子節點為 $11$ 與 $8$，先和較小的 $8$ 交換，得到：

$$[8,11,35,60,45,72]$$

最後的 heap tree 為：

        8
      /   \
    11     35
   /  \    /
 60   45  72

② AVL tree 刪除 $35$

核心觀念

雙向環狀串列的每個節點都有 prev 與 next 指標。若串列非空，頭尾相接：

• head->prev 指向 tail
• tail->next 指向 head

push_back(d) 要把新節點接在原本的 tail 後方，並更新 tail。空串列則需讓新節點同時成為 head 與 tail，且自行形成環。

解題方法

分成空串列與非空串列處理：

1. 空串列：建立新節點，令 prev、next 都指向自己，再令 head、tail 都指向新節點。
2. 非空串列：新節點的前一個節點設為舊 tail，下一個節點設為 head；接著更新舊尾節點與頭節點的連結，最後將 tail 更新為新節點。

核心觀念

後序運算式的規則是：運算子遇到時，從堆疊取出右運算元與左運算元，組合成

$$\text{左運算元}\ \text{運算子}\ \text{右運算元}$$

二元運算式必須滿足：

$$\text{運算元數}=\text{運算子數}+1$$

解題方法

題目文字給出的後序式為：

$$AB*CDEF+/$$

其中運算元為 $A,B,C,D,E,F$，共 $6$ 個；運算子為 $*,+ ,/$，共 $3$ 個。

但完整二元後序式需要 $6-1=5$ 個運算子，因此題目少了 $2$ 個運算子。

依序使用堆疊處理：

讀入符號	堆疊內容
$A$	$A$
$B$	$A,B$
$*$	$AB*$
$C$	$AB*,C$
$D$	$AB*,C,D$