用c语言实现二叉树的层次遍历
时间: 2023-10-24 21:07:02 浏览: 55
二叉树的层次遍历可以使用队列数据结构来实现。具体实现步骤如下:
1. 定义一个队列结构体,并实现队列的入队和出队操作。
2. 定义一个二叉树结构体,并实现二叉树的创建和节点的插入操作。
3. 实现二叉树的层次遍历。首先将根节点入队,然后进入循环,每次从队列中取出一个节点,输出该节点的值,并将其左右子节点依次入队。直到队列为空。
下面是完整的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 队列结构体
typedef struct queue {
int *data;
int front;
int rear;
} Queue;
// 初始化队列
void initQueue(Queue *q, int size) {
q->data = (int *)malloc(sizeof(int) * size);
q->front = q->rear = 0;
}
// 入队
void enqueue(Queue *q, int value) {
q->data[q->rear++] = value;
}
// 出队
int dequeue(Queue *q) {
return q->data[q->front++];
}
// 判断队列是否为空
int isEmpty(Queue *q) {
return q->front == q->rear;
}
// 二叉树节点结构体
typedef struct node {
int value;
struct node *left;
struct node *right;
} Node;
// 创建节点
Node* createNode(int value) {
Node *node = (Node *)malloc(sizeof(Node));
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点
void insertNode(Node **root, int value) {
if (*root == NULL) {
*root = createNode(value);
} else if (value < (*root)->value) {
insertNode(&((*root)->left), value);
} else {
insertNode(&((*root)->right), value);
}
}
// 层次遍历
void levelOrder(Node *root) {
if (root == NULL) {
return;
}
Queue q;
initQueue(&q, 100);
enqueue(&q, root->value);
while (!isEmpty(&q)) {
int value = dequeue(&q);
printf("%d ", value);
if (root->left != NULL) {
enqueue(&q, root->left->value);
}
if (root->right != NULL) {
enqueue(&q, root->right->value);
}
}
}
int main() {
Node *root = NULL;
insertNode(&root, 5);
insertNode(&root, 3);
insertNode(&root, 7);
insertNode(&root, 1);
insertNode(&root, 4);
insertNode(&root, 6);
insertNode(&root, 8);
levelOrder(root);
return 0;
}
```
注意,上面的代码中,队列的大小是固定的,因此如果二叉树的深度过大,有可能会溢出。为了避免这种情况,可以使用动态数组来实现队列。此外,上面的代码只输出了节点的值,如果需要输出节点的其他信息,可以在节点结构体中添加相应的字段,并在层次遍历时输出。