台綜大B30 計概114 第九題 解答 ※ 販售必究 ※ 台灣綜合大學, 資訊管理系, 轉學考

Q9.  對於給定的表列 ( A ( B ( E ( K, L), F, W ), C ( G ), D ) )：

A) 畫出對應的多路樹 (multi-way tree)；

B) 將多路樹轉換為二元樹 (binary tree)，並畫出該二元樹。

Ans:

A) 多路樹 (Multi-way Tree)

規則：

• 每個節點可以有多個子節點。

• 括號中的內容表示該節點的子節點。

分析

• 根節點：A

• A 的子節點：B, C, D

• B 的子節點：E, F, W

• E 的子節點：K, L

• C 的子節點：G

• D 沒有子節點

多路樹結構圖

        A
      / | \
     B  C  D
   / | \   \
  E  F  W   -
 / \
K   L
|
-

• 說明：每個節點用直線連到它的子節點。

• - 表示該節點沒有更多子節點。

---

B) 將多路樹轉換為二元樹 (Binary Tree)

轉換規則 (左子 + 右兄弟表示法 Left-child, Right-sibling)

1. 每個節點的 第一個子節點 成為 左子節點 (left child)。

2. 其他子節點依序成為 右兄弟 (right sibling)。

轉換步驟

• A 左子節點 → B

• B 右兄弟 → C，C 右兄弟 → D

• B 的左子節點 → E

• E 右兄弟 → F，F 右兄弟 → W

• E 的左子節點 → K

• K 右兄弟 → L

• C 的左子節點 → G

• D 沒有子節點

對應二元樹結構圖

        A
       /
      B
     / \
    E   C
   / \   \
  K   F   D
   \   \
    L   W
       /
      G

為了更清楚，我整理成標準二元樹表示：

A
|
B
| \
E  C
| \  \
K  F  D
 \   \
  L   W
      |
      G