C# 資料結構 - 二元樹廣度優先遍歷 (Level Order) 實作 (5)

6.3.2 二元樹寬度優先遍歷 (BFS/Level Order)

逐層從左至右訪問節點，不使用遞迴，改用佇列 (Queue) 輔助。

演算法步驟

1. 根節點入佇列
2. 佇列非空時：出佇列取得節點 D，訪問 D
3. D 左子節點存在則入佇列
4. D 右子節點存在則入佇列，重複步驟 2

程式碼實作

public void LevelOrder() // 寬度優先遍歷
{
    Queue queue = new Queue();
    queue.Enqueue(_head); // 根節點入佇列
    while (queue.Count > 0)
    {
        Node node = (Node)queue.Dequeue(); // 出佇列
        Console.Write(node.ToString());    // 訪問
        if (node.Left != null) queue.Enqueue(node.Left);
        if (node.Right != null) queue.Enqueue(node.Right);
    }
}

測試程式

var bTree = new BinaryTree("ABCDE#F"); // # 表空節點
bTree.LevelOrder();
// 輸出: A B C D E F

遍歷順序與二元樹循序儲存陣列索引順序一致。