二叉树的层序遍历 C代码
时间: 2024-05-11 17:12:07 浏览: 14
二叉树的层序遍历是一种按照树的层级顺序遍历节点的方法,也称为广度优先搜索。我们可以使用队列来实现二叉树的层序遍历。具体实现方法如下:
```c
// Definition for a binary tree node.
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 队列结构体定义
struct Queue {
struct TreeNode* data[10000];
int front;
int rear;
};
void initQueue(struct Queue* queue) {
queue->front = 0;
queue->rear = 0;
}
bool isEmpty(struct Queue* queue) {
return queue->front == queue->rear;
}
bool isFull(struct Queue* queue) {
return queue->front == (queue->rear + 1) % 10000;
}
void push(struct Queue* queue, struct TreeNode* node) {
if (isFull(queue)) {
return;
}
queue->data[queue->rear] = node;
queue->rear = (queue->rear + 1) % 10000;
}
struct TreeNode* pop(struct Queue* queue) {
if (isEmpty(queue)) {
return NULL;
}
struct TreeNode* node = queue->data[queue->front];
queue->front = (queue->front + 1) % 10000;
return node;
}
int* levelOrder(struct TreeNode* root, int* returnSize) {
if (!root) {
*returnSize = 0;
return NULL;
}
int* result = (int*)malloc(sizeof(int) * 1000);
struct Queue queue;
initQueue(&queue);
push(&queue, root);
int index = 0;
while (!isEmpty(&queue)) {
struct TreeNode* node = pop(&queue);
result[index++] = node->val;
if (node->left) {
push(&queue, node->left);
}
if (node->right) {
push(&queue, node->right);
}
}
*returnSize = index;
return result;
}
```