C语言二叉树层序遍历：原理、代码实现与队列详解

层序遍历的核心思路

层序遍历不同于深度优先搜索，它需要“按层”处理节点。具体逻辑如下：

1. 入队根节点：将二叉树的根节点加入队列等待处理。
2. 循环处理：只要队列不为空，就取出队首节点进行访问。
3. 扩展子节点：当访问一个节点时，若其存在左子节点，则将左子节点加入队列；若存在右子节点，则将右子节点加入队列。
4. 层级记录：通过记录当前队列的大小，可以精确划分每一层的节点范围，便于分行输出。

上述图片展示了待遍历的二叉树结构。对于该树，正确的层序遍历顺序应依次为：A → B → C → D → E。

关键数据结构定义

为了实现这一算法，我们需要定义两个核心结构体：
NODE 用于表示二叉树的节点，包含数据域和左右孩子指针；
QUEUE 用于表示队列，这里采用带头结点的链式队列，包含头尾指针以支持高效的插入和删除操作。

typedef struct node {
    char data;
    struct node *lchild;
    struct node *rchild;
}NODE, *PNODE;

typedef struct qnode {
    PNODE pnode;
    struct qnode *next;
}QNODE, *PQNODE;

typedef struct queue {
    PQNODE front;
    PQNODE rear;
    int size;
}QUEUE, *PQUEUE;

其中，front指向头结点，rear指向尾节点，size用于快速判断队列是否为空及统计当前层节点数。

第1步：构建测试用的二叉树

为了验证算法，首先需要创建一个特定的二叉树。下面的 CreateTree 函数手动分配内存并链接节点，构建了图片中的测试用例：

PNODE CreateTree(void) {
    // 分配7个节点内存
    PNODE pA = malloc(sizeof(NODE));
    PNODE pB = malloc(sizeof(NODE));
    PNODE pC = malloc(sizeof(NODE));
    PNODE pD = malloc(sizeof(NODE));
    PNODE pE = malloc(sizeof(NODE));

    // 赋值
    pA->data = 'A'; pB->data = 'B'; pC->data = 'C';
    pD->data = 'D'; pE->data = 'E';

    // 建立连接关系 (对应图片结构)
    pA->lchild = pB; pA->rchild = pC;  // A的孩子是B和C
    pB->lchild = NULL; pB->rchild = NULL; // B是叶子节点
    pC->lchild = pD; pC->rchild = NULL;  // C的左孩子是D
    pD->lchild = NULL; pD->rchild = pE;  // D的右孩子是E

    return pA;
}

第2步：实现队列基础操作

层序遍历依赖队列的三个基本操作：初始化、入队（enQueue）、出队（deQueue）。

1. 初始化队列：创建一个带头结点的空队列，头尾指针均指向该头结点。

2. 入队操作：在队尾创建新节点，将指针域设为NULL，并更新尾指针。

3. 出队操作：保存头结点后的第一个节点，将其从链表中摘下。若该节点是最后一个节点，需同时更新尾指针指向头结点以防止悬垂指针，最后释放内存。

// 初始化
void initQueue(PQUEUE pQ) {
    pQ->front = pQ->rear = malloc(sizeof(QNODE));
    if (!pQ->front) exit(-1); // 防止内存分配失败
    pQ->front->next = NULL;
    pQ->size = 0;
}

// 入队
void enQueue(PQUEUE pQ, PNODE pnode) {
    PQNODE pNew = malloc(sizeof(QNODE));
    if (!pNew) exit(-1);
    pNew->pnode = pnode;
    pNew->next = NULL;
    pQ->rear->next = pNew;
    pQ->rear = pNew;
    pQ->size++;
}

// 出队
bool deQueue(PQUEUE pQ, PNODE *ppnode) {
    if (pQ->front->next == NULL) {
        printf("Queue empty!");
        return false;
    }
    PQNODE tmp = pQ->front->next;
    *ppnode = tmp->pnode;
    pQ->front->next = tmp->next;
    if (tmp->next == NULL)
        pQ->rear = pQ->front; // 特殊处理最后一个节点
    free(tmp);
    pQ->size--;
    return true;
}

第3步：编写层序遍历主逻辑

levelTraversal 函数是整个算法的核心。利用 while (Q.size) 控制外层循环，确保所有节点都被处理。

在内层循环中，我们使用变量 levelSize 记录当前层的节点总数。对于每个节点：
1. 调用 deQueue 取出节点并打印。
2. 检查该节点的左右子节点，若不为空则依次调用 enQueue 加入队列。
这种方法能自然地将同一层的节点分组输出，清晰展示遍历的层级过程。

void levelTraversal(PNODE pnode) {
    if (!pnode) return;
    
    QUEUE Q;
    PNODE tmp;
    initQueue(&Q);
    enQueue(&Q, pnode); // 根节点入队
    
    int level = 0;
    while (Q.size) {
        level++;
        int levelSize = Q.size; // 固定当前层的数量
        printf("traversal level %d have %d nodes: ", level, levelSize);
        
        for (int i=0; i<levelSize; i++) {
            deQueue(&Q, &tmp);
            printf("%c, ", tmp->data);
            
            // 左右孩子入队
            if (tmp->lchild) enQueue(&Q, tmp->lchild);
            if (tmp->rchild) enQueue(&Q, tmp->rchild);
        }
        printf("\n");
    }
}

执行结果与分析

编译并运行上述代码后，控制台输出如下：

层序遍历结果:
traversal level 1 have 1 nodes: A,
traversal level 2 have 2 nodes: B, C,
traversal level 3 have 1 nodes: D,
traversal level 4 have 1 nodes: E,

结果解读：
- 第一层只有根节点 A。
- 第二层有 B 和 C，它们分别是 A 的左、右孩子，符合层序遍历“从左到右”的规则。
- 第三层只有 D，它是 C 的左孩子（C 无右孩子，故跳过）。
- 第四层只有 E，它是 D 的右孩子。

该实现通过标准的链式队列解决了二叉树的广度优先搜索问题，代码结构清晰，适合作为学习C语言数据结构与算法的参考案例。

以上就是C语言实现二叉树层序遍历的详细内容，更多关于C语言数据结构与算法的资料请关注本站其它相关文章！