C语言实现二叉树的层序遍历

在C语言中实现二叉树的层序遍历（也称为广度优先搜索，BFS）通常使用队列来实现。层序遍历会按照从上到下、从左到右的顺序访问二叉树的节点。以下是一个示例代码，展示了如何在C语言中实现二叉树的层序遍历： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树节点结构 typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode; // 定义队列结构 typedef struct QueueNode { TreeNode* treeNode; struct QueueNode* next; } QueueNode; typedef struct Queue { QueueNode* front; QueueNode* rear; } Queue; // 初始化队列 void initQueue(Queue* q) { q->front = q->rear = NULL; } // 判断队列是否为空 int isEmpty(Queue* q) { return q->front == NULL; } // 入队 void enqueue(Queue* q, TreeNode* node) { QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); newNode->treeNode = node; newNode->next = NULL; if (q->rear == NULL) { q->front = q->rear = newNode; return; } q->rear->next = newNode; q->rear = newNode; } // 出队 TreeNode* dequeue(Queue* q) { if (isEmpty(q)) { return NULL; } QueueNode* temp = q->front; TreeNode* node = temp->treeNode; q->front = q->front->next; if (q->front == NULL) { q->rear = NULL; } free(temp); return node; } // 创建新节点 TreeNode* createNode(int data) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->data = data; newNode->left = newNode->right = NULL; return newNode; } // 层序遍历 void levelOrderTraversal(TreeNode* root) { if (root == NULL) return; Queue q; initQueue(&q); enqueue(&q, root); while (!isEmpty(&q)) { TreeNode* current = dequeue(&q); printf("%d ", current->data); if (current->left != NULL) enqueue(&q, current->left); if (current->right != NULL) enqueue(&q, current->right); } } // 主函数示例 int main() { // 创建二叉树 TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); root->right->left = createNode(6); root->right->right = createNode(7); // 进行层序遍历 printf("层序遍历结果: "); levelOrderTraversal(root); printf("\n"); return 0; } ``` 这个示例代码展示了如何定义二叉树节点结构、队列结构以及实现层序遍历的各个函数。通过队列的先进先出特性，可以实现二叉树的层序遍历。

### C语言实现二叉树层序遍历 以下是使用C语言实现二叉树层序遍历的一个完整示例。该方法通常借助队列来完成，因为层序遍历本质上是一种广度优先搜索（BFS），而队列的数据结构特性非常适合这种需求。 #### 定义二叉树节点结构 首先定义二叉树的节点结构以及创建二叉树的方法： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树节点结构 typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right; } TreeNode; // 创建新节点 TreeNode* createNode(int value) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->val = value; newNode->left = NULL; newNode->right = NULL; return newNode; } ``` #### 使用队列实现层序遍历 为了实现层序遍历，可以采用循环的方式模拟队列操作。这里通过动态分配内存的方式来管理队列中的元素。 ```c #define MAX_QUEUE_SIZE 100 void levelOrderTraversal(TreeNode* root) { if (!root) return; // 如果根节点为空，则直接返回 // 初始化队列 TreeNode* queue[MAX_QUEUE_SIZE]; int front = 0, rear = 0; // 将根节点入队 queue[rear++] = root; while (front != rear) { // 当队列不为空时继续处理 TreeNode* currentNode = queue[front++]; printf("%d ", currentNode->val); // 访问当前节点 // 将左子节点加入队列（如果存在） if (currentNode->left) { queue[rear++] = currentNode->left; } // 将右子节点加入队列（如果存在） if (currentNode->right) { queue[rear++] = currentNode->right; } } } ``` 以上代码实现了基于数组的简单队列机制，并完成了二叉树的层序遍历[^2]。 #### 测试代码 下面是一个完整的测试程序，用于验证上述层序遍历算法的功能。 ```c int main() { // 构建一棵简单的二叉树 TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); // 执行层序遍历并打印结果 printf("Level Order Traversal: "); levelOrderTraversal(root); printf("\n"); return 0; } ``` 运行此程序后，输出将是 `Level Order Traversal: 1 2 3 4 5`，这表示按照从上到下、从左至右的顺序访问了所有的节点。 --- ### 注意事项 - 队列大小应根据实际应用调整，或者改用更灵活的动态数据结构替代固定长度数组。 - 上述代码未考虑边界情况（如极端大输入或特殊形状的树），在生产环境中需进一步优化和增强鲁棒性。 ---