利用一个队列,实现对一颗二叉树的层序遍历 。c语言
时间: 2024-03-14 17:44:38 浏览: 25
好的,下面是C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
typedef struct QueueNode {
TreeNode* data;
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* val) {
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
node->data = val;
node->next = NULL;
if (isEmpty(q)) {
q->front = node;
} else {
q->rear->next = node;
}
q->rear = node;
}
TreeNode* dequeue(Queue* q) {
if (isEmpty(q)) {
return NULL;
}
TreeNode* val = q->front->data;
QueueNode* tmp = q->front;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(tmp);
return val;
}
void levelOrder(TreeNode* root) {
if (root == NULL) {
return;
}
Queue q;
initQueue(&q);
enqueue(&q, root);
while (!isEmpty(&q)) {
int size = getSize(&q);
for (int i = 0; i < size; i++) {
TreeNode* node = dequeue(&q);
printf("%d ", node->val);
if (node->left) {
enqueue(&q, node->left);
}
if (node->right) {
enqueue(&q, node->right);
}
}
printf("\n");
}
}
```
这里我们定义了`TreeNode`结构体来表示二叉树的节点,定义了`QueueNode`结构体来表示队列节点,以及`Queue`结构体来表示队列。然后实现了一些常用的队列操作,例如初始化队列(`initQueue`)、判断队列是否为空(`isEmpty`)、入队(`enqueue`)和出队(`dequeue`)等。
最后,我们实现了`levelOrder`函数来进行二叉树的层序遍历。在函数中,我们首先判断根节点是否为空,如果为空,则直接返回。否则,我们定义一个队列`q`,将根节点入队,然后开始循环。在循环中,我们每次取出队首元素,输出它的值,并将其左右子节点(如果存在的话)依次入队。这样就完成了一层的遍历。我们不断重复这个过程,直到遍历完整棵树。
希望能够帮到你!