【数据结构】二叉树——层序遍历

一、层序遍历

层序遍历是一种广度优先遍历

以图上二叉树为例，层序遍历就是按照二叉树的深度一层一层进行遍历
遍历顺序：

A B C D E F G H

二、层序遍历（递归）

若用递归方式解决层序遍历
我们可以先算出二叉树的深度
然后按照不同深度 k 进行遍历
每次向下遍历就 k–
当 k == 1 时就是第 k 层的数据
以此来实现层序遍历

//层序遍历(1)
//(先写一个可以遍历某一层的函数，再循环遍历每一层)

//某一层遍历
void BTLevelkOrder(BTNode* php, int k)
{
	if (php == NULL || k == 0)
	{
		return;
	}
	if (k == 1)
	{
		printf("%c ", php->val);
	}
	BTLevelkOrder(php->left, k - 1);
	BTLevelkOrder(php->right, k - 1);
}
//层序遍历二叉树
void BTLevelOrder(BTNode* php)
{
	if (php == NULL)
	{
		return;
	}
	int dep = BTLevelDepth(php);
	for (int i = 1; i <= dep; i++)
	{
		BTLevelkOrder(php, i);
	}
}

三、层序遍历（非递归）

若要用非递归的方式来解决层序遍历
我们先将根节点入队列
然后将根节点出队列，并将该根节点的左右节点人队列
重复该过程，直到队列为空
队列的代码

//层序遍历(2)
//将节点地址依次入队列
void BTLevelOrder(BTNode* php)
{
	//创建队列
	Queue p;
	QueueInit(&p);

	//先将根入队列
	if(php)
		QueuePush(&p, php);

	while (!QueueEmpty(&p))
	{
		//将根位置节点出队列
		QueueDateType cp = QueueFront(&p);
		QueuePop(&p);

		//打印出队列节点的数据
		printf("%c ", cp->val);

		//左右节点不为空入队列
		if (cp->left)
		{
			QueuePush(&p, cp->left);
		}

		if (cp->right)
		{
			QueuePush(&p, cp->right);
		}
	}
	//队列销毁
	QueueDesTroy(&p);
}

四、总结

上面我们学习了递归与非递归的方式去对二叉树进行层序遍历
我们发现递归的代码简介，而且好理解
那我们为什么不用递归而会去研究非递归的方式呢？
因为我们的递归过程会重复调用函数，就会在栈上开辟空间
而栈中空间大小是有限的
若我们的递归深度太深就会有栈溢出的风险
而非递归方式开辟的队列是在堆中开辟的空间会大很多
一般不会出现空间被占满的情况