C语言二叉树层次遍历算法详解与实现

什么是层次遍历

对于一颗二叉树，层次遍历是指从根节点开始，按照从上到下、从左到右的顺序访问每一个结点。在这个过程中，每个结点必须被且仅被访问一次。

实现原理

由于二叉树本身具有递归定义的特性，要实现非递归的层次遍历，最直接的工具是队列（Queue）。队列遵循“先进先出”（FIFO）的原则，这与层级遍历的顺序天然契合：

1. 初始化：将根节点加入空队列。
2. 循环处理：只要队列不为空，就取出队头节点进行访问，并将其左右孩子（如果存在）依次加入队尾。
3. 结束条件：当队列变空时，说明所有层的节点均已被处理完毕。

第1步：定义数据结构

首先定义二叉树节点和链式队列的结构体。链式队列通过指针动态分配内存，便于管理。

typedef struct BTree {
	char data;
	struct BTree* lchild;
	struct BTree* rchild;
} Tree, *BiTree;

typedef struct Queue {
	BiTree data;
	struct Queue* next;
} Qnode, *Queueptr;

typedef struct point {
	Queueptr front; // 头指针
	Queueptr rear;  // 尾指针
} LinkQueue;

第2步：实现链式队列操作

包括初始化队列、入队、判断空队列以及出队四个核心函数。这些操作构成了遍历的基础工具。

// 初始化队列：创建头结点
void InitQueue(LinkQueue* qu) {
	qu->front = qu->rear = (Queueptr)malloc(sizeof(Qnode));
	if (qu->front == NULL)
		return;
}

// 入队操作：新节点连接在队尾
void enQueue(LinkQueue* qu, BiTree S) {
	if (S == NULL) return; // 空节点不入队
	Queueptr p = (Queueptr)malloc(sizeof(Qnode));
	if (p == NULL) return;
	p->data = S;
	p->next = NULL;
	qu->rear->next = p;
	qu->rear = p;
}

// 判断队列是否为空
int QueueEmpty(LinkQueue qu) {
	if (qu.front != qu.rear)
		return 1; // 非空
	else
		return 0; // 为空
}

// 出队操作：移除并返回队头元素
BiTree deQueue(LinkQueue* qu) {
	if (qu->front == qu->rear) return NULL;
	Queueptr p = qu->front->next;
	BiTree q = p->data;
	qu->front->next = p->next;
	if (qu->rear == p) 
		qu->rear = qu->front;
	free(p);
	return q;
}

第3步：主遍历逻辑与二叉树创建

结合上述队列操作，实现具体的层次遍历函数 ShowCengci，并通过递归方式创建测试用的二叉树。

BiTree InitTree() { // 二叉树的递归创建示例
	BiTree T = (BiTree)malloc(sizeof(Tree));
	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 ShowCengci(BiTree T) {
	LinkQueue qu;
	InitQueue(&qu);
	if(T==NULL) return; // 防止空树传入
	enQueue(&qu, T); // 根节点入队
	while (QueueEmpty(qu)) {
		BiTree S = deQueue(&qu); // 节点出队
		printf("%c ", S->data);
		if (S->lchild != NULL) enQueue(&qu, S->lchild); // 左孩子入队
		if (S->rchild != NULL) enQueue(&qu, S->rchild); // 右孩子入队
	}
}

完成判断

当程序运行输出节点数据序列，且控制台无报错退出时，即表示层次遍历算法执行成功。输出顺序应符合该树的层级结构（例如：根 → 左子 → 右子 → 下一层最左...）。

简要总结

以上就是 C 语言利用队列实现二叉树层次遍历的详细内容。该方法通过标准的 BFS（广度优先搜索）思路，清晰地将树结构线性化，是掌握数据结构中递归与非递归转换的经典案例。更多关于 C 语言二叉树遍历的资料请关注本站其它相关文章！