Lesson 37: 二叉树层序遍历 (BFS)

练习任务

难度: 中

实现 levelorder(root) 函数,用队列辅助进行二叉树的层序遍历(Breadth-First Search,广度优先搜索)。按层从上到下、从左到右打印每个节点的字符。

学以致用: 这道题要求复用 Lesson 35 的环形队列思想--用数组 + front/rear 双指针 + 取模实现辅助队列。唯一变化是队列存储的元素类型从 int 变为 struct node*。二叉树已由 build_tree 按层序构建好。

本课共有 2 组测试用例:

input:  "A B C D E . . . . ."  -> output: A B C D E
input:  "A . ."                -> output: A

提示: BFS 的核心循环是"出队 -> 访问 -> 左右孩子入队"。队列存储 struct node* 指针,不是字符。初始状态是根节点入队,循环条件是队列非空,每轮出队一个节点、访问它、然后将其左右孩子(如果存在)入队。

---

核心知识点

• BFS vs DFS: 层序遍历(BFS)用队列,前中后序(DFS)用栈(递归隐式)
• 队列元素类型泛化: int -> struct node*,指针也是一种数据,可以放入任何数组
• BFS 核心循环: 出队 -> 访问(打印) -> 左孩子入队 -> 右孩子入队
• 按层分组技术: "当前层大小 = rear - front",每层开始时的差值恰好是当前层节点数
• BFS 保证"最近先达": 先访问离根近的节点--这是无权图最短路径的理论基础
• 完全二叉树检测: 层序遍历中遇到第一个 NULL 后,不应再出现非 NULL 节点
• 队列最大长度 = 树的最宽层节点数。退化链表时队列长度 = 1
• Dijkstra = BFS + 优先队列: 将普通队列升级为优先队列,处理有权图的最短路径

---

代码框架

37_binary_tree_level_order.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 256

struct node {
    char ch;
    struct node *left, *right;
};
struct node *make_node(char ch) {
    struct node *p = malloc(sizeof(*p));
    p->ch = ch;
    p->left = p->right = NULL;
    return p;
}

/* 按层序构建二叉树(token 流,'.' 表示空节点) */
struct node *build_tree(char *tokens) {
    // 已提供: 用队列 BFS 构建
    // ...
}

/* 用队列实现层序遍历(BFS)
 * 队列中存储 struct node* 指针,而非字符 */
void levelorder(struct node *root) {
    // 在这里实现 levelorder:
    // 1. if (root == NULL) return;
    // 2. struct node *queue[MAX];
    //    int front = 0, rear = 0;
    // 3. queue[rear++] = root;          -- 根入队
    // 4. while (front < rear) {
    //        struct node *cur = queue[front++];  -- 出队
    //        printf("%c ", cur->ch);             -- 访问
    //        if (cur->left)  queue[rear++] = cur->left;
    //        if (cur->right) queue[rear++] = cur->right;
    //    }
}

int main(void) {
    char line[256];
    fgets(line, sizeof(line), stdin);

    struct node *root = build_tree(line);
    levelorder(root);
    printf("\n");
    return 0;
}

阅读骨架后思考: 队列为什么存指针而不是字符?如果只存字符会丢失什么信息?front 和 rear 的变化规律是什么?

TIP

先不要往下翻看参考解答。回顾 Lesson 35 的环形队列,将元素类型从 int 改为 struct node*,其余逻辑完全一致。画一个 3 层树,手动模拟队列的入队/出队过程,验证输出顺序。

---

深度讲解

1. BFS vs DFS: 队列 vs 栈

1.1 两种搜索策略的对比

        A
       / \
      B   C
     / \
    D   E

层序 (BFS):  A -> B -> C -> D -> E    (逐层,先近后远)
             第0层   第1层   第2层

前序 (DFS):  A -> B -> D -> E -> C    (一路向下,到底回溯)

维度	DFS (前中后序)	BFS (层序)
数据结构	栈(递归隐式调用栈)	队列(显式数组)
策略	深度优先: 沿一条路径走到底再回溯	广度优先: 先访问距离近的,逐层扩展
遍历方式	递归函数调用(自动管理状态)	循环 + 显式维护队列
首次访问根	前序先访问,中序后序较晚	立即(第一层第一个)
典型应用	BST 有序输出、表达式求值、序列化	最短路径、层级打印、完全二叉树判定
空间复杂度	O(h) 递归栈深度(h=树高)	O(w) 队列大小(w=树最宽层)

NOTE

递归的"隐式栈"和 BFS 的"显式队列"本质上是同一种思想的两种实现: DFS = 后进先出(LIFO), BFS = 先进先出(FIFO)。选择哪种取决于你需要"先深入再返回"还是"先探索探再深入"。

1.2 为什么 BFS 用队列?

BFS 的需求:
  1. 先访问根节点 A
  2. 按从左到右顺序访问 A 的孩子 B、C
  3. 按从左到右顺序访问 B 的孩子 D、E
  4. 按从左到右顺序访问 C 的孩子...

关键矛盾:
  当我们访问 B 时,D 和 E 还没有被访问
  当我们访问 C 时,D 和 E 应该已经进入"待访问"队列

队列的 FIFO 特性恰好满足:
  A 入队 -> 出队 A, 孩子 B、C 入队(排在队列后面)
  B 出队 -> 孩子 D、E 入队(排在 C 后面)
  C 出队 -> ...
  D 出队 -> ...
  E 出队 -> ...

队列保证了"先入队的先被访问" => "离根近的先被访问" => BFS!

2. 队列元素类型的泛化: int -> struct node*

2.1 从 Lesson 35 的环形队列说起

queue_evolution.c

// Lesson 35: 队列存储 int
int queue[MAX];
int front = 0, rear = 0;
queue[rear++] = int_value;      // 入队整数
int val = queue[front++];       // 出队整数

// Lesson 37: 队列存储 struct node*
struct node *queue[MAX];
int front = 0, rear = 0;
queue[rear++] = root;           // 入队指针
struct node *cur = queue[front++];  // 出队指针

关键思想: 队列不关心存储什么类型的数据,只管理"先进先出"的顺序。指针也是一种数据(一个内存地址),可以放入任何类型的数组。C++ 的 std::queue<T> 和 Java 的 Queue<T> 都是这一思想的体现。

2.2 为什么必须存指针?

why_pointer.c

// 错误做法: 队列存 char
char queue[MAX];
queue[rear++] = root->ch;         // 只存了字符 'A'

// 问题: 出队时只知道 'A',不知道:
//   - 'A' 有左孩子吗? -> 无法访问 node->left
//   - 'A' 有右孩子吗? -> 无法访问 node->right

// 正确做法: 队列存 struct node*
struct node *queue[MAX];
queue[rear++] = root;             // 存入整个节点的指针
// 出队时可以通过 cur->left 和 cur->right 访问孩子

存指针的本质原因是: BFS 需要从当前节点"发散"到其孩子节点。只存字符数据会丢失树的结构信息。

3. BFS 核心循环: 出队 -> 访问 -> 入队左右

3.1 算法伪代码与逐步跟踪

算法:
  if (root == NULL) return;
  queue[rear++] = root;                    // ① 根入队
  while (front < rear) {                   // ② 队列非空
    cur = queue[front++];                  // ③ 出队
    printf("%c ", cur->ch);               // ④ 访问
    if (cur->left)  queue[rear++] = cur->left;   // ⑤ 左孩子入队
    if (cur->right) queue[rear++] = cur->right;  // ⑥ 右孩子入队
  }

3.2 完整逐步跟踪

以 5 个节点的树为例:

        A
       / \
      B   C
     / \
    D   E

初始
  queue = [A]                         front=0, rear=1
  已输出: (空)

第 1 轮循环
  cur = queue[0] = A  (出队)
  front = 1
  打印 "A "

  A 的左孩子 B 入队: queue[1] = B, rear = 2
  A 的右孩子 C 入队: queue[2] = C, rear = 3

  循环结束: queue = [A, B, C]         front=1, rear=3
  已输出: A

第 2 轮循环
  cur = queue[1] = B  (出队)
  front = 2
  打印 "B "

  B 的左孩子 D 入队: queue[3] = D, rear = 4
  B 的右孩子 E 入队: queue[4] = E, rear = 5

  循环结束: queue = [A, B, C, D, E]   front=2, rear=5
  已输出: A B

第 3 轮循环
  cur = queue[2] = C  (出队)
  front = 3
  打印 "C "

  C 没有孩子

  循环结束: queue = [A, B, C, D, E]   front=3, rear=5
  已输出: A B C

第 4 轮循环: cur = D -> 打印 "D " -> front=4
第 5 轮循环: cur = E -> 打印 "E " -> front=5

front==rear -> 队列空,循环终止
最终输出: A B C D E

4. 按层分组:"当前层大小 = rear - front"

4.1 为什么需要按层分组?

基础 BFS 输出是扁平序列 "A B C D E",无法区分层级。如果我们需要逐行打印每层节点(如打印树形结构),需要识别层边界。

4.2 核心技巧

level_grouping.c

/* 按层分组的 BFS */
void levelorder_by_level(struct node *root) {
    if (root == NULL) return;
    struct node *queue[MAX];
    int front = 0, rear = 0;
    queue[rear++] = root;

    while (front < rear) {
        int levelSize = rear - front;   // 当前层有多少个节点!
        for (int i = 0; i < levelSize; i++) {
            struct node *cur = queue[front++];
            printf("%c ", cur->ch);
            if (cur->left)  queue[rear++] = cur->left;
            if (cur->right) queue[rear++] = cur->right;
        }
        printf("\n");  // 每层结束换行
    }
}

原理: 每轮外循环开始时,rear - front 恰好等于当前层的节点数。因为上一层的所有节点已经出队完毕,下一层的所有节点已经入队完毕(但还未出队)。

第 1 轮开始: front=0, rear=1, levelSize=1 -> 处理第 0 层 [A]
  处理完后: front=1, rear=3 (B,C 已入队)
第 2 轮开始: front=1, rear=3, levelSize=2 -> 处理第 1 层 [B,C]
  处理完后: front=3, rear=5 (D,E 已入队)
第 3 轮开始: front=3, rear=5, levelSize=2 -> 处理第 2 层 [D,E]

5. BFS 的关键性质

1. 按层访问: 距离根相同的节点在同一轮被访问
2. 先近后远: 先入队的先出队 -> 保证先访问离根近的节点
3. 入队顺序决定访问顺序: 先左后右入队 -> 同层从左到右访问
4. 最短路径基础: BFS 在无权图中的首次相遇就是最短路径

6. 完全二叉树检测

层序遍历中,遇到第一个 NULL 节点后,后续所有节点也必须是 NULL--否则不是完全二叉树。

is_complete.c

int is_complete(struct node *root) {
    if (root == NULL) return 1;
    struct node *queue[MAX];
    int front = 0, rear = 0;
    queue[rear++] = root;
    int nullFound = 0;

    while (front < rear) {
        struct node *cur = queue[front++];
        if (cur == NULL) {
            nullFound = 1;
        } else {
            if (nullFound) return 0;  // NULL 之后出现非 NULL
            queue[rear++] = cur->left;
            queue[rear++] = cur->right;
        }
    }
    return 1;
}

7. Dijkstra = BFS + 优先队列

BFS 在无权图中找到最短路径。有权图中,需要将普通队列升级为优先队列(每次选距离最小的节点扩展),这就是 Dijkstra 算法的核心思想:

BFS:    普通队列(FIFO) -> 无权图最短路径
Dijkstra: 优先队列(最小堆) -> 有权图最短路径

这将在 Lesson 46 中深入学习。

---

参考解答

练习: BFS 层序遍历完整实现

solution_37_binary_tree_level_order.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 256

struct node {
    char ch;
    struct node *left, *right;
};
struct node *make_node(char ch) {
    struct node *p = malloc(sizeof(*p));
    p->ch = ch;
    p->left = p->right = NULL;
    return p;
}

struct node *build_tree(char *tokens) {
    if (!tokens || !*tokens) return NULL;
    char *tok = strtok(tokens, " \n");
    if (!tok || *tok == '.') return NULL;
    struct node *root = make_node(*tok), *queue[MAX];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        struct node *cur = queue[front++];
        tok = strtok(NULL, " \n");
        if (tok && *tok != '.') {
            cur->left = make_node(*tok);
            queue[rear++] = cur->left;
        }
        tok = strtok(NULL, " \n");
        if (tok && *tok != '.') {
            cur->right = make_node(*tok);
            queue[rear++] = cur->right;
        }
    }
    return root;
}

void levelorder(struct node *root) {
    if (root == NULL) return;
    struct node *queue[MAX];
    int front = 0, rear = 0;
    queue[rear++] = root;                  // 根入队

    while (front < rear) {
        struct node *cur = queue[front++]; // 出队
        printf("%c ", cur->ch);           // 访问
        if (cur->left)  queue[rear++] = cur->left;
        if (cur->right) queue[rear++] = cur->right;
    }
}

int main(void) {
    char line[256];
    fgets(line, sizeof(line), stdin);
    struct node *root = build_tree(line);
    levelorder(root);
    printf("\n");
    return 0;
}

核心逻辑:

1. 空树判空: if (root == NULL) return; 是第一道防线。
2. 队列存指针: struct node *queue[MAX]--与 Lesson 35 的区别仅是元素类型。
3. 入队顺序: 先左后右,保证同层从左到右访问。
4. 循环终止: front == rear 时队列为空。

对照检查: 队列存了 struct node* 吗?根节点先入队了吗?循环条件是 front < rear 吗?出队后才访问吗?左右孩子按顺序入队了吗?

---

课堂讨论

1. BFS 用队列,DFS 用栈--为什么这两种数据结构恰好对应这两种搜索策略?
2. 队列里存 char 而不是 struct node* 会有什么后果?出队后还能访问到孩子的信息吗?
3. "当前层大小 = rear - front"这个技巧为什么能正确识别层边界?举例说明。
4. 如何用层序遍历判断一棵树是不是完全二叉树?描述算法逻辑。
5. 如果树是一条链表(每个节点只有右孩子),层序遍历的行为是什么样的?队列最大长度是多少?

讨论答案

Q1: 为什么 BFS 用队列,DFS 用栈?

这是两种搜索策略的本质决定的。

BFS = 广度优先 = 先发现先探索 -> FIFO -> 队列
  新发现的节点加到队尾,队头先处理

DFS = 深度优先 = 后发现先探索 -> LIFO -> 栈
  新发现的节点压入栈顶,栈顶先处理

具体例子: 处理节点 A,其孩子为 B、C

BFS: queue = [A]
  出队 A -> 发现 B、C -> 入队 B、C: queue = [B, C]
  出队 B -> B 的孩子入队 -> queue = [C, D, E]
  出队 C -> ...
  顺序: A, B, C, D, E  (层级顺序)

DFS: stack = [A]
  弹出 A -> 发现 B、C -> 压入 B、C: stack = [B, C]
  弹出 C -> C 的孩子压入 -> stack = [B, ...]
  顺序: A, C, .... (深度顺序,与入栈顺序有关)

Q2: 队列存 char 会有什么后果?

// 错误: 队列存 char
char queue[MAX];
queue[rear++] = root->ch;    // 存入 'A'

// 出队时只有字符,没有树结构信息:
char c = queue[front++];
printf("%c ", c);            // 打印 'A'
// 无法知道 A 的左孩子是 B、右孩子是 C!
// 因此无法继续 BFS

// 正确: 队列存 struct node*
struct node *queue[MAX];
queue[rear++] = root;        // 存入整个节点的地址
// 出队后可以通过 cur->left 和 cur->right 访问孩子

根本原因: BFS 需要从节点"发散"到其孩子,这需要节点的完整指针信息。只存字符会丢失结构信息。

Q3: rear - front 为什么等于当前层大小?

以三层树 A(B,C)(D,E,F,G) 为例:

初始: front=0, rear=1, levelSize=1 -> 第 0 层 [A]
  处理 A: 出队 A, 入队 B、C
  处理后: front=1, rear=3
  levelSize=3-1=2 -> 第 1 层 [B,C]
  
  处理 B: 出队 B, 入队 D、E
  处理 C: 出队 C, 入队 F、G
  处理后: front=3, rear=7
  levelSize=7-3=4 -> 第 2 层 [D,E,F,G]

原理:
  每轮开始时,上一层的所有节点已全部出队(front 已推进)
  下一层的所有节点已全部入队(rear 已推进)
  两者差值 = 刚入队但尚未出队的节点数 = 当前层大小

Q4: 如何检测完全二叉树?

完全二叉树定义: 除最后一层外,每层都填满;最后一层从左到右填满。

检测算法(层序遍历):
  1. 层序遍历,包括 NULL 也入队
  2. 遇到第一个 NULL 后,设标志位
  3. 继续遍历,如果标志位为真且遇到非 NULL -> 不是完全二叉树
  4. 遍历完都没有违反 -> 是完全二叉树

例子:
  树 A(B,C):        队列为 [A, B, C] -> 完全二叉树
  树 A( ,C):        队列为 [A, NULL, C] -> NULL 后出现非 NULL -> 不是

Q5: 退化成链表时 BFS 的行为?

树: A -> B -> C -> D  (每个节点只有右孩子)

BFS 过程:
  初始: queue = [A]
  第 1 轮: 出 A, 右孩子 B 入队 -> queue = [B]
  第 2 轮: 出 B, 右孩子 C 入队 -> queue = [C]
  第 3 轮: 出 C, 右孩子 D 入队 -> queue = [D]
  第 4 轮: 出 D, 无孩子 -> queue = []

输出: A B C D  (退化为顺序访问!)

队列最大长度: 1  (始终只有 1 个元素)
BFS 在退化树上退化为普通的顺序遍历。

---

课后练习

1. 按层逐行打印: 修改 BFS,使每层占一行输出。例如树 A(B,C)(D,E) 输出: A \n B C \n D E

   知识点提示: 使用 rear - front 技巧获取每层大小,外层 while + 内层 for。

2. 计算树的宽度: 树的宽度定义为节点数最多的那一层的节点数。编写 int tree_width(struct node *root) 返回树的宽度。

   知识点提示: BFS 遍历时,记录每层开始时 rear - front 的最大值。

3. 自底向上层序遍历: 修改 BFS,从最底层开始向上逐层打印。提示: 可以先正常 BFS 收集每层结果,再反向输出。

   知识点提示: 用一个二维数组或链表存储每层的节点列表,BFS 收集完毕后逆序输出。

4. BFS 最短路径查找: 在二叉树中查找目标字符 target,用 BFS 返回从根到目标节点的距离(边的数量)。若未找到返回 -1。

   知识点提示: BFS 按层遍历,第 k 层出队时所有节点距离根都是 k。首先遇到 target 时返回当前层数。

---

参考资料

• 《算法导论》第 22 章 广度优先搜索 -- BFS 的严格分析与正确性证明
• 《数据结构与算法分析 - C 语言描述》§4 树 -- 树的遍历与 BFS 实现
• Lesson 35 环形队列 -- 队列基础实现(前置知识)
• Lesson 36 DFS 遍历 -- BFS 的对比方(DFS)
• Lesson 46 Dijkstra -- BFS + 优先队列的进阶应用

"The best way to understand BFS is to trace the queue by hand. Every dequeue reveals a new level of the tree." -- Anonymous