一維串列二元搜尋樹廣度優先搜尋 (BFS)

 在一維串列表示的二元搜尋樹中，進行廣度優先搜尋 (BFS) 可以使用佇列 (Queue) 來實現。BFS 的遍歷順序是按層級逐層從左到右訪問所有節點。對於每個節點，先訪問該節點的左子節點，再訪問右子節點。

一維串列的 BFS 實現

使用 collections.deque 來建立佇列，這樣可以高效地從左側取出元素並將新元素添加到右側。

在一維串列中：

• 根節點位於索引 0。
• 對於位於索引 i 的節點：
  • 左子節點位於索引 2 * i + 1。
  • 右子節點位於索引 2 * i + 2。

---

BFS 程式碼實現

以下是使用佇列的 BFS 實現方式：

from collections import deque

def bfs(tree):
    if not tree:
        return []
    
    queue = deque([0])  # 初始佇列中加入根節點的索引
    result = []
    
    while queue:
        i = queue.popleft()  # 取出當前節點的索引
        if i >= len(tree) or tree[i] is None:
            continue
        
        # 訪問當前節點
        result.append(tree[i])
        
        # 將左子節點和右子節點的索引加入佇列
        left_child = 2 * i + 1
        right_child = 2 * i + 2
        queue.append(left_child)
        queue.append(right_child)
    
    return result

---

測試 BFS 程式碼

使用以下測試資料來測試 BFS 函式。假設樹如下所示，並以一維串列形式存儲：

        5
       / \
      3   7
     / \ /
    2  4 6
   /
  1

在一維串列中的表示為：[5, 3, 7, 2, 4, 6, None, 1]

# 建立一維串列表示的二元搜尋樹
bst = [5, 3, 7, 2, 4, 6, None, 1]

# 執行 BFS
print("廣度優先搜尋 (BFS):", bfs(bst))  # 預期輸出 [5, 3, 7, 2, 4, 6, 1]

結果解析

廣度優先搜尋按層級順序輸出節點值，因此預期結果為 [5, 3, 7, 2, 4, 6, 1]。

---

BFS 運作原理簡述

1. 將根節點的索引 0 放入佇列。
2. 每次從佇列中取出一個節點的索引，訪問該節點，並將其左子節點和右子節點的索引放入佇列。
3. 重複以上步驟直到佇列為空。

這種方法保證每個節點按層級順序被訪問一次。