Python 應用鄰接表實作樹的教材

 

以 Python 應用鄰接表實作樹的教材

---

教材目標

1. 了解什麼是鄰接表以及其在樹結構中的應用。
2. 學習如何使用鄰接表表示樹。
3. 掌握基於鄰接表的基本樹操作，如遍歷、計算高度與直徑等。
4. 通過實際問題練習，鞏固樹的基礎知識與鄰接表操作。

---

1. 鄰接表的介紹

什麼是鄰接表？

• 鄰接表是一種高效表示圖和樹的數據結構。
• 每個節點存儲一個列表，其中包含與該節點直接相連的節點。

為什麼用鄰接表來表示樹？

• 占用空間少，特別適合稀疏圖或樹。
• 適合於樹的遍歷操作（例如 DFS、BFS）。

鄰接表的表示方法：

• 使用 Python 的 defaultdict 實現鄰接表。

from collections import defaultdict

# 範例樹的鄰接表表示
tree = defaultdict(list)
tree[1] = [2, 3]
tree[2] = [1, 4, 5]
tree[3] = [1]
tree[4] = [2]
tree[5] = [2]

print(tree)  # {1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}

---

2. 使用鄰接表建構樹

輸入樹的節點與邊：

• 節點數量 n。
• 接下來輸入 n−1 條邊，描述樹的父子關係。

Python 實作：

from collections import defaultdict

# 建構樹
tree = defaultdict(list)
n = int(input("輸入節點數量: "))
for _ in range(n - 1):
    a, b = map(int, input("輸入邊 (空格分隔): ").split())
    tree[a].append(b)
    tree[b].append(a)

print("鄰接表表示的樹：", dict(tree))

範例輸入：

5
1 2
1 3
2 4
2 5

範例輸出：

鄰接表表示的樹： {1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}

---

3. 樹的基本操作

操作 1：深度優先搜尋（DFS）

DFS 的應用場景：

• 遍歷樹的所有節點。
• 計算樹的高度或查找某節點。

DFS 實作：

def dfs(node, parent):
    print(node, end=" ")  # 訪問節點
    for neighbor in tree[node]:
        if neighbor != parent:  # 避免回到父節點
            dfs(neighbor, node)

# 測試
dfs(1, -1)  # 從節點 1 開始

範例輸出：

1 2 4 5 3

---

操作 2：計算樹的高度

樹的高度：

• 根節點到最遠葉子節點的距離。

DFS 計算樹的高度：

def tree_height(node, parent):
    height = 0
    for neighbor in tree[node]:
        if neighbor != parent:
            height = max(height, tree_height(neighbor, node))
    return height + 1

# 測試
print("樹的高度：", tree_height(1, -1))  # 從節點 1 開始計算

範例輸出：

樹的高度： 3

---

操作 3：計算樹的直徑

樹的直徑：

• 樹中兩個節點間的最長距離。

兩次 DFS 計算樹的直徑：

1. 第一次 DFS：從任意節點開始，找到最遠的節點。
2. 第二次 DFS：從該最遠節點開始，再次找到最遠節點，這段距離即為樹的直徑。

Python 實作：

def dfs_diameter(node, parent, depth):
    farthest_node = node
    max_depth = depth
    for neighbor in tree[node]:
        if neighbor != parent:
            new_depth, new_farthest = dfs_diameter(neighbor, node, depth + 1)
            if new_depth > max_depth:
                max_depth = new_depth
                farthest_node = new_farthest
    return max_depth, farthest_node

# 第一次 DFS
_, farthest = dfs_diameter(1, -1, 0)

# 第二次 DFS
diameter, _ = dfs_diameter(farthest, -1, 0)
print("樹的直徑：", diameter)

範例輸出：

樹的直徑： 3

---

4. 綜合應用：解決問題

應用 1：找出所有葉子節點

葉子節點是沒有子節點的節點。

Python 實作：

def find_leaves():
    leaves = []
    for node in tree:
        if len(tree[node]) == 1:  # 只有一個鄰接節點的就是葉子
            leaves.append(node)
    return leaves

# 測試
print("樹的葉子節點：", find_leaves())

範例輸出：

樹的葉子節點： [4, 5, 3]

---

應用 2：找到某節點的子節點

給定節點，找出其所有直接子節點。

Python 實作：

def find_children(node, parent):
    return [neighbor for neighbor in tree[node] if neighbor != parent]

# 測試
print("節點 2 的子節點：", find_children(2, 1))

範例輸出：

節點 2 的子節點： [4, 5]