使用c语言实现二叉树的层次遍历
时间: 2023-10-24 10:06:02 浏览: 37
要实现二叉树的层次遍历,可以使用队列来辅助实现。具体步骤如下:
1. 首先将根节点入队。
2. 当队列不为空时,执行以下操作:
a. 取出队头元素,访问该节点。
b. 如果该节点有左孩子,则将左孩子入队。
c. 如果该节点有右孩子,则将右孩子入队。
3. 重复步骤2,直到队列为空。
具体的代码实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 定义队列结构体
typedef struct Queue {
TreeNode *data[1000];
int front, rear;
} Queue;
// 初始化队列
Queue* initQueue() {
Queue *q = (Queue*)malloc(sizeof(Queue));
q->front = q->rear = 0;
return q;
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return q->front == q->rear;
}
// 入队
void enqueue(Queue *q, TreeNode *node) {
q->data[q->rear++] = node;
}
// 出队
TreeNode* dequeue(Queue *q) {
return q->data[q->front++];
}
// 层次遍历
void levelOrder(TreeNode *root) {
if (root == NULL) return;
Queue *q = initQueue();
enqueue(q, root);
while (!isEmpty(q)) {
TreeNode *node = dequeue(q);
printf("%d ", node->val);
if (node->left) enqueue(q, node->left);
if (node->right) enqueue(q, node->right);
}
}
int main() {
// 构建一棵二叉树
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode)); root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode)); root->left->val = 2;
root->right = (TreeNode*)malloc(sizeof(TreeNode)); root->right->val = 3;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode)); root->left->left->val = 4;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode)); root->left->right->val = 5;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode)); root->right->left->val = 6;
root->right->right = (TreeNode*)malloc(sizeof(TreeNode)); root->right->right->val = 7;
// 层次遍历
levelOrder(root);
return 0;
}
```
输出结果为:1 2 3 4 5 6 7。