请用C语言写出 借助队列实现层次遍历二叉树
时间: 2023-06-18 22:06:20 浏览: 65
下面是借助队列实现层次遍历二叉树的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点
typedef struct TreeNode {
int data;
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 = NULL;
q->rear = NULL;
}
// 入队
void enqueue(Queue* q, TreeNode* data) {
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->data = data;
newNode->next = NULL;
if (q->rear == NULL) {
q->front = newNode;
q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
}
// 出队
TreeNode* dequeue(Queue* q) {
if (q->front == NULL) {
return NULL;
}
QueueNode* temp = q->front;
TreeNode* data = temp->data;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
return data;
}
// 创建二叉树
TreeNode* createBinaryTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = val;
root->left = createBinaryTree();
root->right = createBinaryTree();
return root;
}
// 层次遍历二叉树
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
Queue q;
initQueue(&q);
enqueue(&q, root);
while (q.front != NULL) {
TreeNode* node = dequeue(&q);
printf("%d ", node->data);
if (node->left != NULL) {
enqueue(&q, node->left);
}
if (node->right != NULL) {
enqueue(&q, node->right);
}
}
}
int main() {
TreeNode* root = createBinaryTree();
printf("层次遍历二叉树:");
levelOrderTraversal(root);
return 0;
}
```
以上代码实现了二叉树的层次遍历,利用队列来储存二叉树结点,逐层访问二叉树结点并将其左右孩子结点入队。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)