链式二叉树知识补充：层序遍历与创建销毁

前言

在上篇文章中，我们实现了二叉树的部分基本功能，包括三种遍历，以及统计高度、叶子节点数和指定高度的节点数。本篇文章将会完成二叉树的创建、销毁、层序遍历以及判断是否为完全二叉树等功能的实现。

1. 二叉树的层序遍历及相关应用

1.1 二叉树的层序遍历

除了上一篇文章中介绍到的三种遍历方法，二叉树还存在一种广度遍历方法，即层序遍历。

1.1.1 层序遍历相关概念

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为 1，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第 2 层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

// 层序遍历 void LevelOrder(Btnode* root)

1.1.2 层序遍历的实现

不同于其他三种遍历方法，层序遍历需要借助队列来实现。具体思想：先将根节点放入队列中，然后利用队列的功能函数，输出队头数据，然后将该节点的非空子节点放入队列中，将队头节点出队，再进行下一轮循环，直到队头元素为空。在实际实现中，我们将指向根节点的指针放入队列中，一是为了节省空间，二来可以避免因为 pop 函数导致将树的节点也释放了；同时我们需要将以前实现过的 Queue.h 以及 Queue.c 放入本次项目的文件目录中，然后执行如下操作。

将 Queue.h 以及 Queue.c 添加进来，就可以利用了，同时需要将 Queue.h 中的 int 类型改为指向树的节点的指针。

代码展示：

void LevelOrder(Btnode* root) {
    Que q;
    QueInit(&q);
    if (root != NULL) Quepush(&q, root); // 把树的根节点放进队列
    while (!QueEmpty(&q)) {
        Btnode* front = Quefront(&q); // 取队头元素，为了后面进行访问左右节点
        Quepop(&q);
        printf("%d ", front->data);
        if (front->left) Quepush(&q, front->left);
        if (front->right) Quepush(&q, front->right);
    }
    QueDestroy(&q);
}

1.2 判断是否为完全二叉树

关于这个问题的一些误区：对于满二叉树，我们可以知道确切的数量关系，但是对于完全二叉树，我们只能得到一个大概的范围，所以没办法通过节点的数量来判断，因为一个相同的节点，可以有很多种不同的形态。

对于证明题，最直白的方法就是通过定义来证明。