c语言写一个二叉树广度优先遍历的代码,要求给出每一层的数据
时间: 2024-03-19 11:43:09 浏览: 75
下面是一个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;
/* 初始化队列 */
Queue* initQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
q->front = q->rear = NULL;
return q;
}
/* 判断队列是否为空 */
int isEmpty(Queue* q) {
return q->front == NULL;
}
/* 入队 */
void enqueue(Queue* q, TreeNode* data) {
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
node->data = data;
node->next = NULL;
if (isEmpty(q)) {
q->front = q->rear = node;
} else {
q->rear->next = node;
q->rear = node;
}
}
/* 出队 */
TreeNode* dequeue(Queue* q) {
if (isEmpty(q)) {
return NULL;
} else {
TreeNode* data = q->front->data;
QueueNode* node = q->front;
q->front = q->front->next;
free(node);
return data;
}
}
/* 二叉树广度优先遍历 */
void bfs(TreeNode* root) {
if (root == NULL) {
return;
}
Queue* q = initQueue();
enqueue(q, root);
while (!isEmpty(q)) {
int size = q->rear - q->front + 1;
for (int i = 0; i < size; i++) {
TreeNode* node = dequeue(q);
printf("%d ", node->val);
if (node->left != NULL) {
enqueue(q, node->left);
}
if (node->right != NULL) {
enqueue(q, node->right);
}
}
printf("\n");
}
}
/* 创建二叉树 */
TreeNode* createTree() {
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;
return root;
}
int main() {
TreeNode* root = createTree();
bfs(root);
return 0;
}
```
这个代码中,我们先定义了二叉树节点结构体和队列节点结构体,然后定义了队列结构体和一些队列操作函数。在bfs函数中,我们使用队列实现了广度优先遍历,并且在每一层遍历结束后,输出一个换行符,以便区分不同的层。最后在主函数中,我们创建了一棵二叉树并进行了广度优先遍历。
阅读全文