在數據結構的世界裏，樹是一種非常重要的非線性結構。遍歷樹的方法有很多，其中廣度優先搜索（Breadth-First Search，簡稱BFS）是一種經典的方法。顧名思義，BFS會按照“廣度”優先的原則訪問節點——也就是說，先訪問距離根節點最近的所有節點（同一層的節點），再訪問下一層的節點。這種按層次遍歷的方式，也常被稱爲“層次遍歷”。
爲什麼要學BFS？¶
在樹的問題中，很多場景需要按層次處理節點。比如，計算樹的高度時，BFS能逐層累加層數；判斷一棵樹是否是完全二叉樹，也需要按層次檢查節點的存在性；甚至一些路徑問題，比如求從根到葉子的最短路徑，BFS也能高效解決。掌握BFS，能幫我們更清晰地處理樹中的層次關係問題。
BFS的實現步驟（以二叉樹爲例）¶
BFS的核心是使用“隊列”（Queue）這種數據結構來輔助遍歷。隊列的特點是“先進先出”（FIFO），正好符合BFS按層次處理節點的需求。具體步驟如下：
- 初始化隊列：首先將根節點入隊。如果樹爲空（根節點不存在），則直接結束遍歷。
- 循環處理隊列：只要隊列不爲空，就執行以下操作：
- 取出隊首節點（隊首元素），訪問該節點（例如打印節點值）。
- 將該節點的子節點（通常按“左子節點優先，再右子節點”的順序）依次入隊。 - 終止條件：當隊列爲空時，所有節點都已訪問完畢，遍歷結束。
舉個例子理解BFS過程¶
爲了更直觀，我們用一個具體的二叉樹來模擬BFS的遍歷過程。假設我們有這樣一棵二叉樹：
1
/ \
2 3
/ \
4 5
節點值分別是：根節點1，左子節點2、右子節點3；節點2的左子節點4、右子節點5；其他節點無子女。
模擬BFS過程：
- 初始狀態：隊列中只有根節點1，即 [1]。
- 第一次循環：取出隊首節點1，訪問1。將1的子節點（先左後右）2、3入隊，隊列變爲 [2, 3]。
- 第二次循環：取出隊首節點2，訪問2。將2的子節點4、5入隊，隊列變爲 [3, 4, 5]。
- 第三次循環：取出隊首節點3，訪問3。3無子女，隊列入隊操作無變化，隊列變爲 [4, 5]。
- 第四次循環：取出隊首節點4，訪問4。4無子女，隊列變爲 [5]。
- 第五次循環：取出隊首節點5，訪問5。5無子女，隊列變爲空。
此時遍歷結束，訪問順序爲：1 → 2 → 3 → 4 → 5，這正是按層次遍歷的結果。
關鍵點總結¶
- 隊列的作用：隊列是BFS的“導航器”，確保按順序處理每一層節點。每次取出隊首節點後，必須將其子節點入隊，才能保證下一層節點被依次處理。
- 子節點入隊順序：通常二叉樹按“左子節點優先，再右子節點”入隊，其他類型樹（如多叉樹）則按子節點自然順序入隊。
- 時間複雜度：每個節點僅入隊和出隊一次，因此爲O(n)（n爲節點總數）。
- 空間複雜度：最壞情況下（如完全二叉樹最後一層），隊列最多存儲n/2個節點，因此爲O(n)。
通過隊列實現的BFS，能清晰地按層次遍歷樹中的所有節點。掌握這一方法，能幫助你高效解決樹的層次相關問題，爲後續更復雜的算法學習打下基礎。