二叉树的层序遍历

二叉树的层序遍历

二叉树的遍历，有4种方式，前面我们已经学习了3种方式：前中后序遍历。

1. 思路讲解及举例

现在我们再来学一下二叉树的层序遍历。

那层序遍历的思想是什么呢，又该如何实现呢？

我们一起来看一下：

🆗，我们还来看这棵二叉树：

层序遍历就是从第一层开始，一层一层的往下遍历，每一层从左到右进行遍历。

对于这棵二叉树，它的层序遍历就是1 2 4 3 5 6

思想很简单，那如何用代码实现呢？

要实现层序遍历，在这里我们借助队列来实现：

怎么做呢？

我们先让根结点入队列，然后如果队列不为空，就出对头数据，并把对头数据的孩子结点带入队列，然后继续出对头数据，再将其孩子带入队列，依次循环往复，直到队列为空，就遍历完成了。

最终出队列的顺序就是层序遍历的结果。

2. 代码实现

接下来我们就来实现一下层序遍历：

由于层序遍历需要借助队列实现，所以得先有队列这种数据结构，不过我们之前已经实现过了，直接拿来用就行。

将之前的代码直接添加到当前项目中：

队列有了，我们就来写代码：

当然记得把队列的数据类型修改一下，之前队列我们存的是整型，现在应该存二叉树的结点是吧，但是存结点拷贝比较大，所以存结点指针更好一点：

//层序遍历
void LevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if (root)
        QueuePush(&q, root);
    while (!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        printf("%d ", front->val);
        QueuePop(&q);
        if (front->left)
            QueuePush(&q, front->left);
        if (front->right)
            QueuePush(&q, front->right);
    }
    printf("\n");
    QueueDestroy(&q);
}

我们来测试一下：

是不是跟我们上面的结果一样啊，层序遍历就搞定了。