c语言按层遍历二叉树

### C语言实现二叉树按层遍历 在C语言中，二叉树的层次遍历通常通过队列来完成。其基本原理是利用队列先进先出的特点，依次处理每一层的节点并将其子节点加入到队列中[^4]。 以下是基于队列实现的二叉树层次遍历代码示例： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树节点结构体 typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode; // 创建新节点函数 TreeNode* createNode(int value) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->data = value; newNode->left = NULL; newNode->right = NULL; return newNode; } // 队列节点定义 typedef struct QueueNode { TreeNode* treeNode; struct QueueNode* next; } QueueNode; // 队列头尾指针定义 typedef struct Queue { QueueNode* front; QueueNode* rear; } Queue; // 初始化队列 Queue* initQueue() { Queue* queue = (Queue*)malloc(sizeof(Queue)); queue->front = queue->rear = NULL; return queue; } // 判断队列是否为空 int isEmpty(Queue* queue) { return queue->front == NULL; } // 入队操作 void enqueue(Queue* queue, TreeNode* treeNode) { QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode)); temp->treeNode = treeNode; temp->next = NULL; if (isEmpty(queue)) { queue->front = queue->rear = temp; } else { queue->rear->next = temp; queue->rear = temp; } } // 出队操作 TreeNode* dequeue(Queue* queue) { if (!isEmpty(queue)) { QueueNode* temp = queue->front; TreeNode* result = temp->treeNode; queue->front = queue->front->next; if (queue->front == NULL) { queue->rear = NULL; } free(temp); return result; } return NULL; } // 层次遍历函数 void levelOrderTraversal(TreeNode* root) { if (root == NULL) return; // 如果根节点为空，则直接返回 Queue* queue = initQueue(); // 初始化队列 enqueue(queue, root); // 将根节点入队 while (!isEmpty(queue)) { // 当队列不为空时继续循环 TreeNode* currentNode = dequeue(queue); // 取出队首节点 printf("%d ", currentNode->data); // 打印当前节点的数据 // 左子节点存在则入队 if (currentNode->left != NULL) { enqueue(queue, currentNode->left); } // 右子节点存在则入队 if (currentNode->right != NULL) { enqueue(queue, currentNode->right); } } free(queue); // 释放队列内存 } ``` 上述代码实现了二叉树的层次遍历功能。它首先创建了一个简单的二叉树节点结构 `TreeNode` 和一个用于辅助存储待访问节点的队列 `Queue`。随后，在 `levelOrderTraversal` 函数中完成了层次遍历的核心逻辑。 #### 输出说明 假设输入如下二叉树： ``` 1 / \ 2 3 / \ 4 5 ``` 调用 `levelOrderTraversal(root)` 后，程序会输出：`1 2 3 4 5`。 ---