数据结构：层序遍历 (Level-order Traversal)
目录
推导过程
算法步骤
手动模拟
代码实现
总结与完整代码
书接上文：
数据结构：二叉树的遍历 (Binary Tree Traversals)-CSDN博客
前面三种 DLR, LDR, LRD 都属于“深度优先搜索”(DFS) 的思想，它们会一头扎到底，然后再回溯。
还有一种完全不同的思路：能不能一层一层地访问？
先把第0层（只有根节点）访问了，再把第1层的所有节点访问了，再访问第2层... 这就是层序遍历 (Level-order Traversal)，属于“广度优先搜索”(BFS)。
推导过程
对于我们的示例树:
A <-- 第0层/ \B C <-- 第1层/ \ \D E F <-- 第2层期望的访问顺序是: A B C D E F
这个过程用递归就不那么直观了。我们该如何实现呢？
思考一下，当我们访问完 A 的时候，我们接下来要知道应该去访问 B 和 C。当我们访问完 B，我们应该记住接下来要访问 D 和 E。
这听起来像一个“待办事项”列表。
我们访问一个节点，然后把它的孩子们加到“待办事项”列表的末尾。每次我们都从列表的开头取出一个任务来执行。
这种“先进先出”(First-In, First-Out) 的数据结构是什么？是队列 (Queue)。
算法步骤
-
创建一个队列。
-
如果树不为空，把根节点
A放入队列。 -
当队列不为空时，循环执行以下操作：
a. 从队列头部取出一个节点（我们称之为 current）。
b. 访问 current 节点 (打印它的数据)。
c. 如果 current 有左孩子，把左孩子放入队列尾部。
d. 如果 current 有右孩子，把右孩子放入队列尾部。
手动模拟
-
queue：[ A ] -
取出
A，打印 A。把A的孩子B,C入队。queue：[ B, C ] -
取出
B，打印 B。把B的孩子D,E入队。queue：[ C, D, E ] -
取出
C，打印 C。把C的孩子F入队。queue：[ D, E, F ] -
取出
D，打印 D。D无孩子。queue：[ E, F ] -
取出
E，打印 E。E无孩子。queue：[ F ] -
取出
F，打印 F。F无孩子。queue：[ ] -
队列为空，遍历结束。
最终输出: A B C D E F
代码实现
我们需要自己手动实现一个简单的队列。这里我们用数组来实现一个循环队列。
第1步: 实现队列
// 为队列定义一个较大的容量
#define MAX_QUEUE_SIZE 100// 队列结构
typedef struct {Node* items[MAX_QUEUE_SIZE];int front;int rear;
} Queue;// 创建队列
Queue* createQueue() {Queue* q = (Queue*)malloc(sizeof(Queue));q->front = -1;q->rear = -1;return q;
}// 检查队列是否为空
int isEmpty(Queue* q) {return q->rear == -1;
}// 入队操作
void enqueue(Queue* q, Node* node) {if (q->rear == MAX_QUEUE_SIZE - 1) {printf("Queue is full\n");} else {if (q->front == -1) {q->front = 0;}q->rear++;q->items[q->rear] = node;}
}// 出队操作
Node* dequeue(Queue* q) {Node* item;if (isEmpty(q)) {printf("Queue is empty\n");return NULL;} else {item = q->items[q->front];q->front++;if (q->front > q->rear) {// 当最后一个元素出队后，重置队列q->front = q->rear = -1;}return item;}
}（注意：这是一个简化的队列实现，用于演示层序遍历。在生产环境中可能需要更健壮的实现。）
第2步: 实现层序遍历函数
void levelOrder(Node* root) {// 如果树为空，直接返回if (root == NULL) {return;}// 1. 创建队列Queue* q = createQueue();// 2. 根节点入队enqueue(q, root);// 3. 当队列不为空时循环while (!isEmpty(q)) {// a. 出队Node* current = dequeue(q);// b. 访问节点printf("%c ", current->data);// c. 如果有左孩子，入队if (current->left != NULL) {enqueue(q, current->left);}// d. 如果有右孩子，入队if (current->right != NULL) {enqueue(q, current->right);}}// 别忘了释放队列本身的内存free(q);
}总结与完整代码
我们从“如何不重不漏地访问所有节点”这个问题出发，推导出了访问一个节点时必须处理的三个部分：根(D)、左子树(L)、右子树(R)。
通过排列这三者的顺序，我们自然地得到了三种深度优先的遍历方法：
-
前序遍历 (DLR):
根 -> 左 -> 右 -
中序遍历 (LDR):
左 -> 根 -> 右 -
后序遍历 (LRD):
左 -> 右 -> 根
这三种方法都可以用非常简洁的递归代码实现，代码的结构直接反映了遍历的顺序。
然后，我们探索了一种完全不同的、广度优先的思路，即按层访问，这引出了：
-
层序遍历: 需要借助一个“先进先出”的队列作为辅助数据结构来实现。
下面是包含 main 函数的完整可运行代码，你可以复制到你的开发环境中进行测试：
#include <stdio.h>
#include <stdlib.h>// --- 节点定义 ---
typedef struct Node {char data;struct Node* left;struct Node* right;
} Node;// --- 队列的实现 (为层序遍历准备) ---
#define MAX_QUEUE_SIZE 100
typedef struct {Node* items[MAX_QUEUE_SIZE];int front;int rear;
} Queue;Queue* createQueue() {Queue* q = (Queue*)malloc(sizeof(Queue));q->front = -1;q->rear = -1;return q;
}int isEmpty(Queue* q) {return q->rear == -1;
}void enqueue(Queue* q, Node* node) {if (q->rear == MAX_QUEUE_SIZE - 1) return;if (q->front == -1) q->front = 0;q->rear++;q->items[q->rear] = node;
}Node* dequeue(Queue* q) {if (isEmpty(q)) return NULL;Node* item = q->items[q->front];q->front++;if (q->front > q->rear) {q->front = q->rear = -1;}return item;
}// --- 树的创建 ---
Node* createNode(char data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->left = NULL;newNode->right = NULL;return newNode;
}Node* build_example_tree() {Node* root = createNode('A');root->left = createNode('B');root->right = createNode('C');root->left->left = createNode('D');root->left->right = createNode('E');root->right->right = createNode('F');return root;
}// --- 遍历函数的实现 ---// 前序遍历: D -> L -> R
void preOrder(Node* root) {if (root == NULL) return;printf("%c ", root->data);preOrder(root->left);preOrder(root->right);
}// 中序遍历: L -> D -> R
void inOrder(Node* root) {if (root == NULL) return;inOrder(root->left);printf("%c ", root->data);inOrder(root->right);
}// 后序遍历: L -> R -> D
void postOrder(Node* root) {if (root == NULL) return;postOrder(root->left);postOrder(root->right);printf("%c ", root->data);
}// 层序遍历
void levelOrder(Node* root) {if (root == NULL) return;Queue* q = createQueue();enqueue(q, root);while (!isEmpty(q)) {Node* current = dequeue(q);printf("%c ", current->data);if (current->left != NULL) {enqueue(q, current->left);}if (current->right != NULL) {enqueue(q, current->right);}}free(q);
}// --- 主函数 ---
int main() {Node* root = build_example_tree();printf("Pre-order Traversal (前序遍历): ");preOrder(root);printf("\n");printf("In-order Traversal (中序遍历): ");inOrder(root);printf("\n");printf("Post-order Traversal (后序遍历):");postOrder(root);printf("\n");printf("Level-order Traversal (层序遍历):");levelOrder(root);printf("\n");// 在这里添加释放树内存的代码（后序遍历是最佳方式）return 0;
}希望这个从第一性原理出发的、逐步推导的过程能帮助你彻底理解二叉树的遍历。