目录

实现思路

代码实现

前言

之前介绍了二叉树的前、中、后序三种遍历，采用的是递归的方式。今天我们来学习另外一种遍历方式——层序遍历。层序遍历不容小觑，虽然实现方法并不难，但是它所采取的思路是很值得学习的，与前三者不同，我们将采用非递归的方式实现。

层序遍历：从二叉树的根节点出发（设根节点所在为第一层），从上到下，从左到右的一次访问第一、第二、第三......层的节点。

正文

实现思路

我们将采用一种数据结构——队列来实现层序遍历。以这样的二叉树为例：

我们知道队列有个重要的性质，只能从队尾进数据，在队头出数据；

因此我们先将 1 入队。

接着让队头的元素 1 出队。在 1 出队的同时有个约定：将 1 所在节点的左、右孩子入队；

接着让队头的元素 2 出队。在 2 出队的同时，将 2 所在节点的左、右孩子入队（若为空节点则不入队）；

队头元素 4 出队，左、右孩子入队；

队头元素 3 出队，左、右孩子入队；

队头元素 5 出队，左、右孩子入队；

......

最后，队列为空即表示所有节点都已访问完毕。

代码实现

因为此处用到了队列的知识

//队列的初始化
void QueueInit(Queue* pq);
//释放malloc出的内存
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头的数据
QDataType QueueFront(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
    QueuePush(&q, root);
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    printf("%d ", front->data);
    QueuePop(&q);
    if(front->left)
      QueuePush(&q, front->left);
    if(front->right)
      QueuePush(&q, front->right);
  }
  printf("\n");
  QueueDestroy(&q);
}