4.4.2. 二叉树(II) 层序遍历与宽度优先搜索¶
前面学习了二叉树的基本知识和链式、顺序两种存储结构的实现方法。但是我们发现，光这些完全不足以有效地使用二叉树结构，甚至无法有效地创建出一棵二叉树。
造成这一问题的原因是树结构的特殊性。对于一棵二叉树中的某一个节点，不能像线性表元素一样有一个确定的毫无歧义的序号来标定它所在的位置。要让计算机程序知道二叉树中某一个节点的位置，需要一条从根节点出发的路径。因此，如果我们只有一系列的数据项是不足以创建出所需要的二叉树的，还需要数据项的路径或确定路径的规则才行。
实际的二叉树节点路径规则是多种多样的，不同的规则能生成出不同的二叉树，比如二叉检索树、红黑树等。这一节我们将介绍一种最简单的层序访问规则，按从上到下的顺序从根节点依次访问直到最底层，在同一层中按照从左到右的顺序依次访问所有节点，遇到空节点直接跳过。这个规则可以归纳为从上到下、从左到右。
如果我们要在二叉树中搜索某个满足特定条件的节点，我们可以按层序逐个节点地扫描搜索，这就是著名的宽度优先搜索（BPS）。当然了，层序访问或宽度优先搜索都不局限于二叉树，事实上任何结构的树都可以按层序规则来访问节点，而宽度优先搜索甚至能用于网状结构（例如图）的搜索。
对一个数据结构中的所有元素按照一定规则完整地进行一次访问，不重复、不遗漏，这一过程称为一次遍历（traversal），按照层序规则进行的遍历就称为层序遍历（layer-order traversal）。层序规则的实现一般要依赖于使用一个队列。
注意
接下来的所有示例程序中我们一律采用链式结构来实现二叉树，毕竟这是最为自然最为常见的一种实现形式。顺序结构一般仅用于完全二叉树，最常见的是用来构造堆结构，我们将在介绍堆的时候再使用。
4.4.2.1. 层序创建完全二叉树¶
给定一个数据项序列，可以按层序规则创建为一棵完全二叉树。在没有对节点定位规则做多余假设的情况下，默认采用层序来构造完全二叉树是最合理的设想了，因为完全二叉树层数最少，空间利用最合理。
设给定了一个长度为 \(n\) 的序列 \(a[0..n-1]\)，显然 \(a[0]\) 是要作为根节点的。\(a[1]\) 和 \(a[2]\) 分别是根节点的左右两个子节点，它们位于树的第2层。随后第3层上的节点为 \(a[3]\) 到 \(a[6]\) 一共4个，依次分别是 \(a[1]\) 的左右子节点和 \(a[2]\) 的左右子节点。依此类推直到最后一层的最后一个节点 \(a[n-1]\)。
如果我们没有一种有效的辅助数据结构，仅是靠序列编号本身来推算数据项应该在哪一个节点上，那么创建过程会非常复杂。比如我们可以计算出来 \(a[10]\) 的所在节点位置应该是第4层左起第4个位置，是其父节点的右儿子。那么接下来就要找到它的父节点，通过计算可以知道是第3层的第2个节点。但是为了定位过去，我们还得再向上找父节点的父节点，即第2层的第1个节点。然后再向上定位到根节点。这是一个不断向上回溯，直到根节点，然后再按照回溯路径一路访问下来的过程，太麻烦了，我们需要一种更好的办法。更好的办法就是用一个队列来作为辅助数据结构，下面我们就来看看怎样做到。假设我们的序列为 {1, 2, 3, 4, 5, 6}，一共6个整数。
第一步先读入第1个数据项1，它一定是根节点。于是我们先创建出一个根节点，放入数据项1，然后将其入队。结果如下图所示，左边为节点队列，右边为生成过程中的二叉树形象：
重要
在实际实现树的链式结构的时候，我们一般都使用指向节点的指针变量而不是直接用节点变量，队列里存放的其实也是指针而不是实际的节点。而且节点都是使用动态内存分配出来的，不是直接定义出节点的变量来。这样就可以更加灵活地引用这些节点，无论作为队列里的元素还是实际的树节点，其实都只是一个指针而已。只有用 delete 语句销毁内存才会使得真正的节点消失，单纯地删除队列元素甚至销毁整个队列都不会导致节点丢失。
接下来我们就要不断地读入后面的数据项，生成节点并将其接在树上正确的位置了。这个过程在程序里肯定是通过一个读数循环来实现的，在讲解时我们一个一个数据项地展示。第二个读入的数据项为2，先生成好节点。然后我们检查队列的队头元素，发现队头指向的节点还没有左儿子，所以新节点就挂在它的左子上，并且让这个新节点入队。我们用白色表示没有子节点的节点，灰色表示只有一个左儿子的节点，于是队列和生成中的二叉树如下图所示：
继续，读入第三个数据项3并生成节点。这时检查队头发现队头所指的节点已经有左儿子了，所以将新节点挂在它的右节点上并且入队。现在这个队头所指的节点已经两个子节点满了，我们用蓝色表示这样的节点。这个节点无法再接受新的子节点，所以我们应该让它出队了。这一波操作完成后的样子如下图：
继续读入第四个数据项4，生成新节点，检查队头所指的节点发现该节点没有左儿子，于是新节点挂在队头节点的左子上并入队：
读入第五个数据项5，生成新节点，检查队头后挂在队头节点的右子上，队头出队，新节点入队：
读入第六个数据项6，生成新节点，检查队头后挂在队头节点的左子上，结果如下：
至此所有数据项全部读完，对应的完全二叉树已经构造完毕。由于队列里存放的元素只是指向节点的指针，所以此时我们可以放心地让整个队列消失，不会对生成好的二叉树产生任何影响。只要我们还记得树根节点的指针，通过这个根指针就能找到整棵树。
下面是实现代码。先定义树节点结构，为了方便起见我们不再使用数据封装的惯例，也不再使用模板技术，而是像在传统的C语言中所做的那样，直接定义好节点结构 Node，外部程序直接访问结构的成员变量，并且我们将指向节点的指针定义为一个单独的自定义数据类型 BiTree，今后在程序中我们全部使用这个指针类型来表示二叉树。然后我们实现一个 create() 函数来创建一棵完全二叉树，数据项依次从标准输入设备读入进来，按照层序规则逐步构建，完成后返回根节点的指针。
#include <queue>
#include <iostream>
using namespace std;
struct Node {
int value;
Node *left;
Node *right;
Node() { left = NULL; right = NULL; }
};
typedef Node *BiTree; // 将节点指针定义为一个自定义类型
BiTree create(int n); // 按层序创建完全二叉树
BiTree create(int n)
{
// 用于创建完全二叉树的队列
queue<BiTree> q;
// 读入第一个数并生成根节点
BiTree root = new Node();
cin >> root->value;
// 根节点放入队列中
q.push(root);
for (int i = 1; i < n; ++i) {
// 读入一个数并生成节点
BiTree node = new Node();
cin >> node->value;
// 如果队首处节点的左子已经有了，那么就将新节点连到它的右子上
// 并且从队列中出队；否则就将新节点连到它的左子上
if (q.front()->left) {
q.front()->right = node;
q.pop();
} else {
q.front()->left = node;
}
// 新节点入队
q.push(node);
}
return root;
}
4.4.2.2. 二叉树的层序遍历¶
光是创建好一棵完全二叉树并没有什么用，数据结构是要用的，用的方式就是访问其中的数据项，最常用的访问方式就是遍历和搜索。搜索只是一个满足特定条件就中止的遍历而已，所以掌握遍历算法是最为重要的。
层序遍历是适用于所有树结构的，不光是完全二叉树，任何树都是分层的，都可以进行层序遍历。按照层序进行节点搜索的过程又叫做宽度优先搜索，是回溯算法中极为重要的一种。
实现层序遍历仍然需要用到一个队列作为辅助。下面还是先看具体的例子，就以前面生成好的二叉树为例。初始的时候我们有一棵节点数为6的二叉树，并初始化一个节点指针队列，将要遍历的二叉树的根节点入队，如下图：
接下来我们要循环地做下面这样的工作直至队列变空：访问队头节点，然后把它的左右两个子节点（如果有的话）依次入队，没有的子节点就直接跳过即可，最后队头节点出队。我们在示例图中把已经访问过的节点用黄色表示。
第1步：队头是根节点1，访问它，然后把它的左儿子2和右儿子3依次入队，最后队头出队：
第2步：访问队头节点2，节点4、5依次入队，节点2出队：
第3步：访问队头节点3，节点6入队，节点3没有右儿子，最后节点3出队：
然后按照相同的规则依次访问队头节点4、5、6，它们都没有子节点，因此访问过程中都没有新节点入队。直到节点6访问完毕从队列中出队，此时队列为空，层序遍历结束：
提示
所谓节点的访问，就是指读取该节点中的数据项，读取之后当然是要用来完成一些操作，比如和某个特定值进行比较等。在一些特殊的场景下也可能是修改数据，但大多数具有特殊用途特定规则的二叉树是不允许修改数据值的，比如二叉检索树，因为数据值会影响节点所在的位置。
最简单的节点访问，当然就是输出该节点的数据了。比如下面这个函数用层序遍历完成树中所有节点数据的输出：
void show_by_layers(BiTree root); // 按层序输出二叉树节点数据（层序遍历，或宽度优先搜索）
void show_by_layers(BiTree root)
{
// 用于层序访问二叉树节点的队列
queue<BiTree> q;
// 根节点入队
q.push(root);
// 访问节点直到队列为空
while (!q.empty()) {
// 如果队头的节点不空，就输出它的数值
// 然后将它的左右子节点（也是左右子树根节点）入队
// 当然也可以先左右子节点入队再输出数值
if (q.front()) {
cout << q.front()->value << endl;
q.push(q.front()->left);
q.push(q.front()->right);
}
// 队头的节点出队
q.pop();
}
}
4.4.2.3. 二叉树的层序销毁¶
还有一个严重的问题，我们的二叉树中所有的节点都是通过 new 语句动态分配的，所以删除节点时就必须用 delete 语句来销毁，有借有还嘛。
那么如果一棵二叉树完全停止使用之后，我们应该立即将其中所有的节点进行销毁，即销毁整棵二叉树。这应该怎么做呢？其实很简单，还是可以通过层序遍历的规则来进行，只不过把销毁节点看作是访问节点。这里唯一要注意的是，层序遍历二叉树的时候每次访问队列中队头节点的同时要把它的子节点按照从左到右的顺序依次入队，这两个步骤谁先谁后都无所谓，但层序销毁二叉树的时候必须先把子节点入队，然后才能销毁掉队头所指的节点，否则就找不到它的子节点了。
接下来还是用前面那棵树作为例子看一看整个销毁的过程，我们用红色表示下一步要销毁的节点，也就是当前队头所指向的那个节点。首先还是把树根节点入队。
现在开始下面这样的循环：将队头所指节点的子节点从左到右依次入队，然后销毁队头所指节点，释放其占用的内存，并进行一次出队。第1轮循环完成后的情况如下图：
下一轮循环将要销毁的队头所指节点为节点2，在图中用红色表示。第2轮循环完成后变成下图的样子：
随后不断循环直到队列为空，整棵树的销毁过程也就结束了：
下面这个函数用来销毁一棵二叉树，别忘了给 Node 结构增加一个析构函数 ~Node() 并在其中调用下面这个函数。这里用到一个奇怪的小技巧：指针的指针。
void destroy(BiTree *root_p); // 按层序销毁二叉树
// 注意这里的参数是指向根节点的指针的指针
// 这是为了能够在销毁之后把根节点设置为空指针
// 如果不在本函数内确保将根节点设为空，那么调用者很容易忘记这一步重要的操作
void destroy(BiTree *root_p)
{
// 用于层序销毁节点的队列
queue<BiTree> q;
// 根节点入队
q.push(*root_p);
// 访问节点直到队列为空
while (!q.empty()) {
// 如果队头的节点不是空节点，则销毁它
// 注意必须要先将左右子树的根节点入队再销毁节点
// 否则就找不回左右子树节点的指针了
if (q.front()) {
q.push(q.front()->left);
q.push(q.front()->right);
delete q.front();
}
// 队头的节点出队
q.pop();
}
*root_p = 0; // 0就是空指针NULL
}
函数的参数可想而知是树根，但是这次参数的类型是 BiTree * 而不是 BiTree，我们知道后者本身就是一个指针类型，是指向节点结构的指针，相当于 Node *。所以这里的参数类型 BiTree * 实际上是指向节点结构的指针的指针，相当于 Node **。
指针的指针，顾名思义，终究还是一个指针，只不过这个指针所指向的变量仍是一个指针。这种二重指针在软件开发中很常用，但在算法程序中却很少用到，甚至要避免使用，因为它太容易让人混乱了。为什么这里我们要用到它呢？因为C++动态内存技术有一条规范，delete 之后应立即把指针设置为空指针。这是因为 delete 只负责释放内存，并不会改变指针的原值，空间释放之后，指针其实还是指向原来的地址的。为了避免误使用已经被释放掉的内存块，我们应该在 delete 后及时把原来的指针置为空。而在一个函数内如果要修改参数的实际值，就要用传引用或者传指针的形式来传递这个参数，如果这个参数本身是指针，那么更加顺理成章的就是用传指针的方式来传指针参数，即参数采用指针的指针的形式。
练习
认真看懂本节所给出的节点结构和三个操作函数，补完 Node 结构的析构函数，然后自己编写 main() 函数，实现以下功能：
输入一个整数 \(6 \lt n \lt 100\)，然后用前 \(n\) 个正整数构造一棵完全二叉树。
按层序输出这棵二叉树中所有节点上的数据。
销毁根节点的左子节点的整棵右子树，然后再次层序输出此二叉树。