树：二叉树的层序遍历算法（超简洁实现及详细分析）

全栈程序员站长

发布于 2022-08-31 11:48:36

9690

发布于 2022-08-31 11:48:36

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

实现思路

我们来看看下图的二叉链表如何实现层序遍历。

层序遍历顺序：ABECDG A为B、E的双亲结点，遍历顺序是根->左->右是不是。而且每个结点都是这样的遍历顺序有木有。那么我们完全可以采用队列的数据结构呗。A入队->然后出队，出队时将其左右孩子入队，循环队列进行出队，每次出队将其左右孩子入队。当队列为空时，整棵树层序遍历完毕。还没明白请看下面过程。 A->出队 队列：E、B B->出队 队列：D、C、E E->出队 队列：G、D、C C->出队 队列：G、D D->出队 队列：G G->出队 队列为空，层序遍历完毕。

二叉树层序遍历算法代码

层序遍历函数

层序遍历核心代码，利用了一个自己底层封装的顺序队列。如果想知道怎么实现的呢，请看线性表：顺序队列算法实现。

//一排一排的遍历 利用队列的特性哟，将根结点入队列 然后然后出入队列，出队列后将其左右孩子结点入队列
//直到队列为空
void SeqTraverse(BiTree tree)
{
	SeqQueue queue = Init_SeqQueue();
	Push_SeqQueue(queue, tree);
	while (!IsEmpty_SeqQueue(queue))
	{
		BiTree root = Pop_SeqQueue(queue);
		printf("%c ", root->data);
		if (root->lchild)
			Push_SeqQueue(queue, root->lchild);
		if(root->rchild)
			Push_SeqQueue(queue, root->rchild);
	}
	printf("\n");
}

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include "SeqQueue.h"
typedef char ElemType;
typedef struct BiNode
{
	ElemType data;
	struct BiNode* lchild;
	struct BiNode* rchild;
}BiNode, *BiTree;

//创建二叉链表
void CreateBiTree(BiTree* tree) 
{
	char c;
	scanf("%c", &c);
	if (c == ' ')
	{
		*tree = NULL;
		return;
	}
	*tree = malloc(sizeof(BiNode));
	(*tree)->data = c;
	CreateBiTree(&(*tree)->lchild);
	CreateBiTree(&(*tree)->rchild);
	return;
}
//二叉链表 递归前序遍历
void PreTraverse(BiTree tree)
{
	if (tree == NULL)
	{
		return;
	}
	printf("%c ", tree->data);
	PreTraverse(tree->lchild);
	PreTraverse(tree->rchild);
}

//一排一排的遍历 利用队列的特性哟，将根结点入队列 然后然后出入队列，出队列后将其左右孩子结点入队列
//直到队列为空
void SeqTraverse(BiTree tree)
{
	SeqQueue queue = Init_SeqQueue();
	Push_SeqQueue(queue, tree);
	while (!IsEmpty_SeqQueue(queue))
	{
		BiTree root = Pop_SeqQueue(queue);
		printf("%c ", root->data);
		if (root->lchild)
			Push_SeqQueue(queue, root->lchild);
		if(root->rchild)
			Push_SeqQueue(queue, root->rchild);
	}
	printf("\n");
}

int main(int argc, char *argv[])
{
	BiTree tree = NULL;
	printf("请前序遍历输入结点：");
	CreateBiTree(&tree);
	printf("前序遍历：");
	PreTraverse(tree);
	printf("\n层序遍历：");
	SeqTraverse(tree);
	
	return 0;
}