C語言二叉樹層序遍歷：隊列實現完整指南

算法核心

層序遍歷（BFS）借助隊列：

1. 根節點入隊
2. 隊列不空時：出隊 → 訪問 → 左右子節點非空則入隊

隊列結構設計（鏈式隊列）

typedef struct QNode {
    BiTree data;
    struct QNode* next;
} QNode;

typedef struct {
    QNode* front;
    QNode* rear;
} LinkQueue;

void InitQueue(LinkQueue* q) {
    q->front = q->rear = (QNode*)malloc(sizeof(QNode));
    q->front->next = NULL;
}

bool EnQueue(LinkQueue* q, BiTree node) {
    QNode* n = (QNode*)malloc(sizeof(QNode));
    if (!n) return false;
    n->data = node;
    n->next = NULL;
    q->rear->next = n;
    q->rear = n;
    return true;
}

bool DeQueue(LinkQueue* q, BiTree* node) {
    if (q->front == q->rear) return false; // 空
    QNode* p = q->front->next;
    *node = p->data;
    q->front->next = p->next;
    if (q->rear == p) q->rear = q->front;
    free(p);
    return true;
}

bool QueueEmpty(LinkQueue* q) {
    return q->front == q->rear;
}

層序遍歷完整函數

void LevelOrder(BiTree T) {
    if (!T) return;
    LinkQueue q;
    InitQueue(&q);
    EnQueue(&q, T);
    BiTree p;
    while (!QueueEmpty(&q)) {
        DeQueue(&q, &p);
        printf("%d ", p->data);
        if (p->lchild) EnQueue(&q, p->lchild);
        if (p->rchild) EnQueue(&q, p->rchild);
    }
    // 釋放隊列頭結點
    free(q.front);
}

關鍵點提示

• 帶頭結點鏈隊列：front==rear 判空，操作統一針對 front->next。
• 入隊在隊尾（rear），出隊在隊頭（front->next）。
• 遍歷結束後記得釋放頭結點，避免記憶體洩漏。

測試主函數

int main() {
    // 構建測試樹
    BiTree root = CreateTree(); // 略
    printf("層序遍歷: ");
    LevelOrder(root);
    printf("\n");
    return 0;
}

總結

二叉樹層序遍歷的關鍵在於隊列的正確實現。掌握「帶頭結點鏈隊列」的入隊/出隊/判空邏輯，即可輕鬆寫出穩健的 BFS 代碼。建議先獨立測試隊列操作，再整合進遍歷函數。