二叉树的层次遍历C语言实现
时间: 2025-06-18 16:05:37 浏览: 8
### 二叉树层次遍历的C语言实现
以下是基于队列数据结构实现二叉树层次遍历的完整代码[^1]:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode* lchild;
struct TreeNode* rchild;
} BiTree;
// 队列定义
#define MAXSIZE 50
typedef struct QueueNode {
int front, rear;
BiTree* data[MAXSIZE];
} LinkQueue;
void InitQueue(LinkQueue* Q) {
Q->front = Q->rear = 0;
}
int IsFull(LinkQueue Q) {
return ((Q.rear + 1) % MAXSIZE == Q.front);
}
int isEmpty(LinkQueue Q) {
return (Q.front == Q.rear);
}
void enQueue(LinkQueue* Q, BiTree* node) {
if (IsFull(*Q)) {
printf("队列已满\n");
return;
}
Q->data[Q->rear] = node;
Q->rear = (Q->rear + 1) % MAXSIZE;
}
BiTree* deQueue(LinkQueue* Q) {
if (isEmpty(*Q)) {
printf("队列为空\n");
exit(0);
}
BiTree* temp = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return temp;
}
// 创建二叉树
BiTree* InitTree() {
BiTree* T = (BiTree*)malloc(sizeof(BiTree));
char data;
scanf("%c", &data);
getchar();
if (data == '#') {
return NULL;
} else {
T->data = data;
printf("请输入%c的左子树:\n", data);
T->lchild = InitTree();
printf("请输入%c的右子树:\n", data);
T->rchild = InitTree();
}
return T;
}
// 层次遍历函数
void LevelOrderTraversal(BiTree* root) {
LinkQueue queue;
InitQueue(&queue);
if (!root) {
return;
}
enQueue(&queue, root);
while (!isEmpty(queue)) {
BiTree* current = deQueue(&queue);
printf("%c ", current->data);
if (current->lchild != NULL) {
enQueue(&queue, current->lchild);
}
if (current->rchild != NULL) {
enQueue(&queue, current->rchild);
}
}
}
int main() {
printf("请输入二叉树(前序输入,'#'表示空节点):\n");
BiTree* treeRoot = InitTree();
printf("\n层次遍历结果为:\n");
LevelOrderTraversal(treeRoot);
return 0;
}
```
#### 关键点解析
1. **队列的作用**
使用队列存储当前层的节点,在访问某个节点的同时将其左右子节点加入队列。当队列中的所有节点都被处理完毕时,即完成了整个二叉树的层次遍历[^2]。
2. **时间复杂度与空间复杂度**
- 时间复杂度:O(n),其中 n 是二叉树中节点的数量。每个节点仅被访问一次。
- 空间复杂度:最坏情况下 O(n),取决于队列的最大长度,通常等于最后一层的节点数量。
3. **边界条件**
如果二叉树为空,则直接返回;否则按照层次顺序逐层访问并打印节点值。
---
阅读全文
相关推荐

















