层序遍历

2026 大纲 四（二）3 二叉树的遍历 · 层序部分（前序见《前序遍历》、中序见《中序遍历》、后序见《后序遍历》）。

层序是四种遍历里唯一不递归的那个

自上而下、每层自左至右。对下面这棵树，层序序列是 A B C D E F：

        A          第 1 层: A
       / \
      B   C        第 2 层: B C
     / \   \
    D   E   F      第 3 层: D E F

前中后序都是从"根、左子树、右子树"这个递归定义里排列出来的，写成代码就是三行递归。层序不在这套体系里——它要求的次序是"离根近的先访问"，这是一个横向的、跨子树的要求，递归的纵向结构表达不了。

所以层序必须换一套驱动结构：队列。而队列的先进先出恰好一次给出两个保证——第 $k$ 层的结点全部排在第 $k+1$ 层之前（层次由浅到深），同层内谁先入队谁先出队，而入队次序正是"双亲从左到右、每个双亲先左后右"（同层从左到右）。

换成栈会怎样：栈后进先出，取出根后压入左右孩子，下一轮取出的就是刚压进去的孩子，于是立刻往深处走——得到的是深度优先的次序，层次结构完全丢失。

为什么不能写成递归：递归调用栈天然是后进先出，函数返回的次序决定了它只能做深度优先。要用递归"模拟"层序，只能靠"逐层重来"（第 $k$ 轮只输出第 $k$ 层）这类做法，时间会退化到 $O(nh)$。这就是层序在教材里被单独列出来的原因。

先看一眼

加载可视化中...

看完你应该确认：队列里同时存在的结点，总是集中在相邻的一两层上——这决定了它的空间瓶颈是树的宽度，而不是高度。

基本实现：出队、访问、两个孩子入队

typedef struct BiTNode {
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void LevelOrder(BiTree T) {
    if (T == NULL) return;
    BiTree queue[MAXSIZE];              // 辅助队列，存的是结点指针
    int front = 0, rear = 0;
    queue[rear++] = T;                  // 根结点入队
    while (front != rear) {             // 队非空
        BiTree p = queue[front++];      // 队头出队
        visit(p);                       // 访问当前结点
        if (p->lchild != NULL)
            queue[rear++] = p->lchild;  // 左孩子先入队，保证同层从左到右
        if (p->rchild != NULL)
            queue[rear++] = p->rchild;  // 右孩子后入队
    }
}

主循环只有三步：出队一个 → 立即访问 → 左孩子右孩子依次入队，队空即止。

这里用的是非循环顺序队列，front 与 rear 只增不回绕，靠 MAXSIZE 开够大来回避假溢出。每个结点恰好入队一次，所以只要 MAXSIZE $>n$ 就不会越界；规范写法是换成循环队列（rear = (rear+1) % MAXSIZE）或链队列，可把空间从 $n$ 降到"最大宽度"。

复杂度：时间 $O(n)$（每个结点恰好入队一次、出队一次、访问一次）；空间 $O(n)$，但准确的说法是队列峰值取决于树的宽度——完全二叉树时峰值恰为 $\lceil n/2\rceil$（出现在最后一个分支结点出队、把孩子送进队列的那一刻），而单支树（退化成链）任一时刻队列里最多只有 1 个结点，空间是 $O(1)$。

单支树恰好是前中后序遍历最费空间的那种树。所以"哪种遍历更省空间"没有统一答案，必须先看树形：树越深，深度优先越费、层序越省；树越宽，反之。两者的最坏情形互不重叠。

按层分组：全部技巧只有一行

基本版输出的是一串扁平序列，分不出层。分层的关键只有一句：每轮外层循环开始时，把当前队列长度记下来。

void LevelOrderByLevel(BiTree T) {
    if (T == NULL) return;
    BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    queue[rear++] = T;
    int level = 0;
    while (front != rear) {
        int cnt = rear - front;      // 关键：此刻队列里恰好是完整的一层
        level++;
        printf("第 %d 层：", level);
        while (cnt--) {              // 一次内层循环刚好处理完这一层
            BiTree p = queue[front++];
            printf("%c ", p->data);
            if (p->lchild) queue[rear++] = p->lchild;
            if (p->rchild) queue[rear++] = p->rchild;
        }
        printf("\n");
    }
}

cnt 为什么就是当前层的结点数？靠一个不变量：进入外层循环时，上一层的结点已全部出队，它们的孩子（即当前层的全部结点）都已入队，且当前层还没有任何结点出队去生成下一层。这个不变量在每一轮开始时都成立。

有了它，一批任务全部变成一行改动：

派生任务	做法
求树的高度	外层循环执行了几轮，树就有几层
求树的最大宽度	取所有轮次中 cnt 的最大值
输出每个结点的层号	用当前的 level
求最后一层的结点	最后一轮外层循环处理的那批
自底向上的层序	把每层结果压栈，最后逐层弹出
之字形（蛇形）遍历	奇数层正序输出、偶数层把该层结果逆序输出

用层序判定完全二叉树

完全二叉树的形态特征是"前 $h-1$ 层满、第 $h$ 层从左到右连续"。翻译成层序遍历的语言就是：

把空孩子也当作结点入队，则一旦从队列中取出一个空结点，此后队列中不允许再出现任何非空结点。

int IsCompleteBinaryTree(BiTree T) {
    if (T == NULL) return 1;                 // 空树按完全二叉树处理
    BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    queue[rear++] = T;
    while (front != rear) {
        BiTree p = queue[front++];
        if (p != NULL) {
            queue[rear++] = p->lchild;       // 注意：空孩子也要入队，不加 if 判断
            queue[rear++] = p->rchild;
        } else {
            // 取出了一个空结点，检查后面是否还有非空结点
            while (front != rear) {
                if (queue[front++] != NULL) return 0;   // 空结点之后还有实结点 → 不完全
            }
        }
    }
    return 1;
}

孩子入队时绝不能加 if (p->lchild) 判断。 加了就等于把空位跳过去，编号空洞被抹平，任何二叉树都会被判成完全二叉树。这是本节最容易写错的一行。

正确性一句话就能说清：若树是完全二叉树，按层序把空位也算上，实结点的编号是 $1..n$ 连续的、空位全部排在 $n$ 之后，所以第一个空结点之后一定全是空；反之若某个实结点排在某个空位之后，说明编号出现了空洞，与"编号 $1..n$ 连续"矛盾。

层序序列能确定什么、不能确定什么

性质	说明
第一个元素是根	与前序相同
单独不能确定二叉树	层序只给出"谁在谁前面"，不给父子归属。层序 A B 对应"B 是 A 的左孩子"与"B 是 A 的右孩子"两棵不同的树
层序 + 中序可唯一确定	层序首元素定根，中序划分左右，再从层序中按归属筛出两组子序列递归
层序 + 前序 / 层序 + 后序不能确定	三者都定不了左右边界，理由与"前序 + 后序不行"相同
完全二叉树的层序序列单独就能确定	顺序存储就是按层序编号放，二者定义等价
不能直接判断祖先关系	X 排在 Y 前面只说明 X 的层次不深于 Y，不说明 X 是 Y 的祖先

第三条要展开说，因为它是层序在真题里唯一被用到的地方。"层序 + 中序"重建的做法：层序的第一个元素是根，用它在中序序列里切一刀分出左右子树；接下来在层序的剩余部分里，最先出现的、属于左子树的那个结点就是左子树的根，右子树同理；对两边递归。

关键在"最先出现"——层序保证浅的结点排在深的前面，所以某棵子树里层序位置最靠前的那个，必然是这棵子树的根。

层序与图 BFS 的逐条对照（对照图那一章时展开）

树的层序遍历就是图的广度优先搜索在树上的特例。

树的层序	图的 BFS	差别的原因
队列驱动，根先入队	队列驱动，起点先入队	相同
不需要 visited[] 数组	必须有 visited[]	树无环、每个结点只有一条来路；图可能有环、有多条路径
"层号"就是到根的边数	"层号"就是到起点的最短路径长度（边数）	同一件事；这正是 BFS 求无权图最短路径 的原理
孩子次序由左右子树决定	邻接点次序由存储结构（邻接表链接顺序）决定	树的左右是有序的

同理，前序遍历是 DFS 在树上的特例。DFS 与 BFS 的分界只有一条：待处理结点存在栈里还是队列里。

考点速记

三条会被反复调用的结论：

1. 队列的 FIFO 同时保证了"层次由浅到深"与"同层从左到右"，这也是层序无法写成递归的原因——递归栈是 LIFO，只能做深度优先。
2. 分层的唯一技巧是"进入外层循环时队列里恰好是完整一层"，由它直接派生出求高度、最大宽度、层号、最后一层、自底向上与之字形。
3. 判完全二叉树时空孩子必须入队；层序的空间瓶颈是宽度，与前中后序的高度正好互补。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）——只有一种，而且层序在其中是配角：

• 给中序 + 层序，重建二叉树后求另一种遍历序列。 层序在这里的作用是每一步指认子树的根：层序里最先出现的、属于当前子树的那个结点就是该子树的根，拿它去中序序列里切分左右，递归下去。手上一定要真的把树画出来——这类题的失分几乎全在"层序里下一个属于哪棵子树"判错了。

层序单独不成为一道选择题的落点，因为它的算法本身没有分支：出队、访问、孩子入队，三行写完。它的价值在于当重建题给的两个序列里有一个是层序时，你要知道怎么用。

易错：判完全二叉树时给孩子入队加了判空。 空洞被抹平，任何树都会被判成完全。

易错：以为层序序列里排在前面的是祖先。 只能说明层次不深于，同层结点也有先后。

易错：认为层序一定比前中后序省空间。 深树上层序省，宽树上深度优先省，两者最坏情形互不重叠。

教材出处

• "此外还有一种按层次遍历二叉树的方式，这种方式按照『从上到下，从左到右』的顺序遍历二叉树……层次遍历不是一个递归过程，层次遍历算法的实现可以借助队列这种数据结构"：严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p125（5.5.1 节）
• 二叉树抽象数据类型中 LevelOrderTraverse(T) 的定义"层序遍历 T，对每个结点访问一次"：印刷 p118
• 完全二叉树的定义（"每一个结点都与深度为 $k$ 的满二叉树中编号从 1 至 $n$ 的结点一一对应"）与"叶子结点只可能在层次最大的两层上出现"：印刷 p119

相关知识

图的广度优先搜索（层序是它在树上的特例）｜BFS 求最短路径（层号即最短边数）｜前序遍历／中序遍历／后序遍历（空间瓶颈与本篇互补）｜由遍历序列构造二叉树｜树与二叉树基本概念｜队列／循环队列｜树与森林

相关文章

• 树与二叉树基本概念
• 前序遍历
• 中序遍历
• 后序遍历
• 由遍历序列构造二叉树
• 线索二叉树
• 二叉排序树（BST）
• 平衡二叉树（AVL）
• 红黑树
• 哈夫曼树
• 堆（大根堆/小根堆）
• 并查集
• 树与森林
• 树与森林的转换

交互体验

前往完整可视化页面 →

真题练习

相关真题（1题）

2026Q32分