《二叉树》——3（层序遍历）

目录

前言：

层序遍历:

解析：

前言：

本文主讲链式二叉树的层序遍历，在前面的张篇blog我们初步实现了链式二叉树递归部分的内容，对于递归算法的学习和思维方式我们仍然需要不断加强，所以将对链式二叉树进行收尾，下一章我们将开启递归算法的题目强化训练。

层序遍历:

typedef struct BTTreeNode* QDataType;
//将链队列中的节点类型改为struct BTTreeNode（二叉树节点的数据类型）

void TreeLevelOrder(TreeNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root == NULL)
	{
		printf("空树\n");
		exit(-1);
	}
	int levelsize = 1;
	QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		while (levelsize--)
		{
			TreeNode* front = QueueFront(&q);
			printf("%d ", front->data);
			if (front->left)
			{
				QueuePush(&q, front->left);
			}
			if (front->right)
			{
				QueuePush(&q, front->right);
			}
			
			QueuePop(&q);
		}
		printf("\n");
		levelsize = QueueSize(&q);
	}
	printf("\n");
	QueueDestroy(&q);
}

层序遍历不需要用到递归的思想，用我们之前学习过的队列的知识就可以实现层序遍历。

这里是用到队列的先进先出的特性。

以上是一颗二叉树，现在要实现该数的层序遍历，最终结果为：

1

2 4

3 5 6

解析：

    Queue q;
	QueueInit(&q);

	if (root == NULL)
	{
		printf("空树\n");
		exit(-1);
	}
	int levelsize = 1;
	QueuePush(&q, root);

 对于这一串代码，就是定义队列并且初始化，并将根节点入队列，再定义一个队列长度，用来接受队列里的节点数，当levelsize为空时，就代表当前层数的节点已经打印完毕。因为是将根节点入队列，而且第一层有且只有一个节点，即根节点，所以levelsize = 1;

while (!QueueEmpty(&q))
	{
		while (levelsize--)
		{
			TreeNode* front = QueueFront(&q);
			printf("%d ", front->data);
			if (front->left)
			{
				QueuePush(&q, front->left);
			}
			if (front->right)
			{
				QueuePush(&q, front->right);
			}
			
			QueuePop(&q);
		}
		printf("\n");
		levelsize = QueueSize(&q);
	}

目前的队列如上图所示。

首先我们需要将定义front指针指向队列的第一个元素。

此时我们需要将root的左右子树入队列，首先我们需要判断左右子树是否为空树。

如果不是空树就入队列。

则有：

而这个时候front指向的节点会被先打印出来，再出队列，这时候front就会指向下一个节点，并且levelsize也为0，因为这时候队列的首数据已经出队列，所以队列中只有两个数据，那么levelsize就会被赋值为2。

如图：

 同样，接下来就是判断front指向的节点的左右子树是否为空，不为空则入队列。

即：

由于levelsize为2，所以程序会打印队列的前两个数据，即24

2打印完后，front就会指向4这个节点，同样也会判断该节点的左右子树是否为空，不为空则入队列。

如图：

然后打印完4的节点后，levelsize又会被赋值为3，用来答应下一层的节点。

如此不断重复，层序遍历则完美实现。