按层遍历二叉树c语言代码
时间: 2023-09-22 13:12:07 浏览: 65
以下是按层遍历二叉树的 C 语言代码:
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树的节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 定义队列的节点结构体
typedef struct QueueNode {
TreeNode *node;
struct QueueNode *next;
} QueueNode;
// 定义队列结构体
typedef struct Queue {
QueueNode *front;
QueueNode *rear;
int size;
} Queue;
// 初始化队列
void initQueue(Queue *q) {
q->front = q->rear = NULL;
q->size = 0;
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return q->size == 0;
}
// 入队
void enqueue(Queue *q, TreeNode *node) {
QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
newNode->node = node;
newNode->next = NULL;
if (isEmpty(q)) {
q->front = q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
q->size++;
}
// 出队
TreeNode *dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty!");
return NULL;
}
QueueNode *temp = q->front;
TreeNode *node = temp->node;
q->front = q->front->next;
free(temp);
q->size--;
return node;
}
// 层序遍历二叉树
void levelOrderTraversal(TreeNode *root) {
if (root == NULL) return;
Queue *q = (Queue *)malloc(sizeof(Queue));
initQueue(q);
enqueue(q, root);
while (!isEmpty(q)) {
int size = q->size;
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 *createNode(int val) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
int main() {
// 创建二叉树
TreeNode *root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
// 层序遍历二叉树
levelOrderTraversal(root);
return 0;
}
```
代码中使用队列实现按层遍历二叉树。首先,创建一个队列,将根节点入队。然后,循环队列,每次取出队列中的一层节点,输出节点值,并将该层节点的子节点入队。重复执行直到队列为空。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)