二元樹廣度優先遍歷（層序遍歷）實作：佇列輔助的非遞歸演算法

為何需要佇列？

前序/中序/後序遍歷皆為深度優先（DFS），天然適合遞歸。廣度優先（BFS）/ 層序遍歷需「逐層處理」：先處理完第 1 層，再處理第 2 層... 這要求先進先出（FIFO）特性，故必須引入佇列暫存待處理節點。

佇列資料結構設計

為簡化實作，採用動態陣列模擬非循環佇列，容量預設為樹的總節點數。

typedef struct _QUEUE {
    int head;           // 隊頭索引
    int tail;           // 隊尾索引
    int length;         // 陣列容量
    TREE_NODE** pHead;  // 儲存節點指標的陣列
} QUEUE;

佇列核心操作

建立佇列（先統計節點數）

int count_all_node_number(const TREE_NODE* pTreeNode) {
    if (NULL == pTreeNode) return 0;
    return 1 + count_all_node_number(pTreeNode->left) + count_all_node_number(pTreeNode->right);
}

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(pQueue);
    memset(pQueue, 0, sizeof(QUEUE));

    pQueue->pHead = (TREE_NODE**)malloc(sizeof(TREE_NODE*) * count);
    assert(pQueue->pHead);
    memset(pQueue->pHead, 0, sizeof(TREE_NODE*) * count);

    pQueue->head = pQueue->tail = 0;
    pQueue->length = count;
    return pQueue;
}

入隊 / 出隊

void insert_node_into_queue(QUEUE* pQueue, TREE_NODE* pNode) {
    if (NULL == pQueue || NULL == pQueue->pHead || NULL == pNode) return;
    pQueue->pHead[pQueue->tail++] = pNode; // 非循環，tail 單調增
}

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++];
}

層序遍歷主流程

QUEUE* traverse_node_by_layer(TREE_NODE* pNode) {
    if (NULL == pNode) return NULL;

    QUEUE* pQueue = create_queue_for_tree(pNode);
    assert(pQueue);

    // 1. 根節點入隊
    insert_node_into_queue(pQueue, pNode);

    // 2. 迴圈：出隊 → 訪問 → 子節點入隊
    while ((pNode = get_node_from_queue(pQueue)) != NULL) {
        // 此處可對 pNode 執行訪問操作（如列印、統計）
        printf("%d ", pNode->data);

        if (pNode->left)  insert_node_into_queue(pQueue, pNode->left);
        if (pNode->right) insert_node_into_queue(pQueue, pNode->right);
    }

    return pQueue; // 返回佇列，pHead 陣列即為層序結果
}

進階應用：賦予節點層級鏈接能力

若需在節點結構中直接支援「下一層節點」存取，只需兩步：

1. 擴充 `TREE_NODE`：新增 `prev`、`next` 指標。
2. 遍歷完成後，依序遍歷 `pQueue->pHead` 陣列，將相鄰元素的 `prev`/`next` 互指。

// 遍歷後補充鏈接
for (int i = 0; i < pQueue->tail - 1; ++i) {
    pQueue->pHead[i]->next = pQueue->pHead[i+1];
    pQueue->pHead[i+1]->prev = pQueue->pHead[i];
}

複雜度分析

• 時間：O(N) — 每節點入隊、出隊各一次。
• 空間：O(N) — 佇列陣列大小 = 樹節點數（最寬層節點數 ≤ N）。

總結

層序遍歷是樹上 BFS 的標準形式，核心在於佇列緩衝跨層節點。本文實作採用動態陣列非循環佇列，邏輯清晰，適合教學與中小型資料量場景。大規模生產環境建議改用循環佇列或 `std::queue`/`CQueue` 成熟容器。