二叉樹廣度優先遍歷：佇列實作與逐層輸出完整指南

二叉樹遍歷常見三種：前序、中序、後序，均屬深度優先策略。而廣度優先遍歷（層序遍歷）鮮少被提及，卻在特定場景（如逐層輸出、最短路徑、樹的序列化）極具價值。其核心差異在於：需要額外資料結構——佇列，利用先進先出（FIFO）特性，確保上一層節點全部處理完畢，再進入下一層。

佇列資料結構設計

為配合樹節點指標存儲，佇列節點資料型別定義為 TREE_NODE**：

typedef struct _QUEUE {
    int head;           // 隊頭索引
    int tail;           // 隊尾索引
    int length;         // 佇列容量
    TREE_NODE** pHead;  // 指標陣列起始位址
} QUEUE;

佇列建立與節點總數計算

建立佇列前需先統計樹的總節點數，以分配足夠記憶體：

QUEUE* create_queue_for_tree(const TREE_NODE* pTreeNode) {
    if (NULL == pTreeNode) return NULL;
    
    int count = count_all_node_number(pTreeNode);  // 遞歸統計節點總數
    QUEUE* pQueue = (QUEUE*)malloc(sizeof(QUEUE));
    assert(NULL != pQueue);
    memset(pQueue, 0, sizeof(QUEUE));
    
    pQueue->pHead = (TREE_NODE**)malloc(sizeof(TREE_NODE*) * count);
    assert(NULL != pQueue->pHead);
    memset(pQueue->pHead, 0, sizeof(TREE_NODE*) * count);
    
    pQueue->head = pQueue->tail = 0;
    pQueue->length = count;
    return pQueue;
}

佇列基本操作：入隊與出隊

本實作採用非循環佇列，邏輯簡潔直觀：

// 入隊：將節點指標存入隊尾，tail 後移
void insert_node_into_queue(QUEUE* pQueue, TREE_NODE* pNode) {
    if (NULL == pQueue || NULL == pQueue->pHead || NULL == pNode) return;
    pQueue->pHead[pQueue->tail++] = pNode;
}

// 出隊：取出隊頭節點，head 後移；隊空返回 NULL
TREE_NODE* get_node_from_queue(QUEUE* pQueue) {
    if (NULL == pQueue || NULL == pQueue->pHead) return NULL;
    if (pQueue->head == pQueue->tail) return NULL;  // 隊空判斷
    return pQueue->pHead[pQueue->head++];
}

層序遍歷核心演算法

標準 BFS 流程：根節點入隊 → 迴圈出隊節點 → 將其左右子節點入隊 → 重複直至佇列為空：

QUEUE* traverse_node_by_layer(TREE_NODE* pNode) {
    if (NULL == pNode) return NULL;
    
    QUEUE* pQueue = create_queue_for_tree(pNode);
    assert(NULL != pQueue);
    
    insert_node_into_queue(pQueue, pNode);  // 根節點入隊
    pNode = get_node_from_queue(pQueue);    // 取出根節點
    
    while (pNode) {
        if (pNode->left)  insert_node_into_queue(pQueue, pNode->left);
        if (pNode->right) insert_node_into_queue(pQueue, pNode->right);
        pNode = get_node_from_queue(pQueue);  // 取出下一個節點
    }
    return pQueue;  // pQueue->pHead 即為層序結果陣列
}

進階應用：在節點結構內嵌雙向鏈表

若需在節點結構中直接支援層序訪問，只需兩步：

1. 在 TREE_NODE 中新增 prev 與 next 指標
2. 遍歷佇列結果陣列 pQueue->pHead，依序串聯 prev/next

此舉將層序關係固化為結構一部分，後續層序操作無需重新建佇列，適合頻繁層序存取的場景。