探索二叉树（上）
二叉树概述
众所周知，二叉树是一种特殊的树形结构。它与链表类似，基本单元是节点，而每个节点都包含值、左子节点的引用和右子节点的引用。二叉树的特点是每个节点最多只有两个子节点，并且二叉树中的子树有左右之分，分为左子树与右子树，它们的顺序不可以颠倒。
二叉树中的一些基本术语
假设我们有一个二叉树 T，根节点为 A，其余节点如图所示：
我们以节点 D 为例，来介绍一些二叉树中的基本术语：
- 根节点：节点 A 是二叉树 T 的根节点；
- 节点：除了节点 D 自身外，A、B、C、E、F 都是节点；
- 叶子节点：除了节点 D 自身外，节点 E、F 都是叶子节点，它们没有任何子节点；
- 祖先：节点 D 的祖先是指从节点 D 到根节点 A 的路径上的所有节点，也就是节点 B 和 A；
- 双亲（节点）：节点 D 的双亲是指节点 D 的直接父节点，也就是节点 B；
- 孩子（节点）：非常可惜，节点 D 是叶子节点，没有孩子节点。但往上看，节点 D 的双亲节点 B 有两个孩子，分别是节点 D 和 E；
- 兄弟（节点）：节点 E 是节点 D 的右兄弟节点，而节点 D 则是节点 E 的左兄弟节点；
- 堂兄弟（节点）：节点 F 是节点 D 的堂兄弟节点，因为它们的双亲节点（B 和 C）是兄弟关系。
此外，借用 Hello Algo 中二叉树一节的图例与其它术语，如下所示：
- 边：连接两个节点的线段，即节点的引用（指针）；
- 节点所在的层：从顶至底递增，根节点所在层为 1；
- 节点的度：节点的子节点的数量。在二叉树中，度的取值范围是 $[0, 2]$；
- 二叉树的高度：从根节点到最远叶节点所经过的边的数量；
- 节点的深度：从根节点到该节点所经过的边的数量；
- 节点的高度：从距离该节点最远的叶节点到该节点所经过的边的数量。
二叉树与度为 2 的树的区别在于：
- 度为 2 的树至少需要有 3 个节点，而二叉树可以为空；
- 二叉树无论节点的孩子数量是否为 2，都需要确定孩子的左右；而度为 2 的树中节点孩子则不需要区分左右，因为这些孩子实际上并没有左右之分。
常见二叉树的种类
二叉树有很多种类，仍然借用 Hello Algo 中的图例来展示，下面将列举一些常见的二叉树种类：
- 满二叉树（完美二叉树）：每个节点都有两个子节点，且所有叶子节点都在同一层；
- 完全二叉树：除了最底层外，其他层构成的二叉树都是满二叉树，相当于从满二叉树的最底层开始，从左到右依次填充或从右往左删除节点；
- 平衡二叉树：任意节点的左子树和右子树的高度差不超过 1；
- 二叉搜索树：对于每个节点，左子树的所有节点的值都小于该节点的值，右子树的所有节点的值都大于该节点的值。
相信能阅读本文的读者应该都或多或少对二叉树的概念及结构有所了解，因此先略过其它一些概念性的内容。
接下来，我们使用 C++ 来实现一些简单的二叉树结构，并编写一些基础的函数来辅助我们探索二叉树。
使用 C++ 定义一个二叉树节点
对 Anawaert 较为熟悉的读者都知道，Anwaert 的惯用编程语言是 C# 与 Python。但由于对于主流的数据结构与算法的描述中，C/C++ 是最常用的编程语言，因此本文将使用 C++ 来实现二叉树。
在大部分使用 C++ 定义的二叉树节点示例中，往往使用的是结构体（struct）。为了实现更好的泛用性，我们使用类（class）来定义二叉树节点，并使用模板（泛型）来扩展节点的值类型。虽然从 C++11 开始，我们可以使用标准库中的 std::shared_ptr 来管理节点的引用，但为了更好地理解二叉树的结构，我们在这里使用裸指针来实现。
#include <iostream>
using namespace std;
template <typename T>
class BinaryTree
{
public:
// 左、右孩子结点对应的指针，默认值为 nullptr
BinaryTree<T>* leftChild = nullptr;
BinaryTree<T>* rightChild = nullptr;
// 当前结点存放的值
T value;
// 构造函数
BinaryTree(T nodeValue);
};
（注：本文为了便于展示变量的类型，采用的是 Type* variable 的形式来定义指针变量，而非 Type *variable 的形式。这样的写法的确不符合 C++ 的命名规范，更像是 C# 的写法，但为了便于阅读，Anawaert 最终还是采用这种写法。对于需要声明多个同类型指针变量的情况，Anawaert 将这些变量分开多行声明。）
接着，我们来实现构造函数：
template <typename T>
BinaryTree<T>::BinaryTree(T nodeValue)
{
value = nodeValue;
}
在有了二叉树节点的定义后，我们可以使用以下的函数来进行节点的创建：
template <typename T>
BinaryTree<T>* createBinaryTreeNode(T nodeValue)
{
return new BinaryTree<T>(nodeValue);
}
createBinaryTreeNode() 函数将返回一个指向新创建的二叉树节点的指针。由于我们使用 new 运算符来创建节点，因此需要注意在使用完毕后尽量使用 delete 运算符进行引用释放，避免产生内存泄漏。当然，如果程序属于一发即弃的类型，或者是一个简单的测试程序，那么就不需要过于担心内存泄漏的问题。
至此，我们可以来检验一下这些内容是否能够正常工作。我们在 main() 函数中创建 3 个二叉树节点，分别为 Root、A 和 B，它们的值分别为 int 类型的 1、2 和 3，其中 A 是 Root 的左孩子，B 是 Root 的右孩子。代码如下：
int main(int argc, char *argv[])
{
BinaryTree<int>* root = createBinaryTreeNode(1);
BinaryTree<int>* a = createBinaryTreeNode(2);
BinaryTree<int>* b = createBinaryTreeNode(3);
root->leftChild = a;
root->rightChild = b;
cout << "Root: " << root->value << "; A: " << root->leftChild->value << "; B: " << root->rightChild->value << endl;
return 0;
}
编译并运行上述代码，输出结果如下：
Root: 1; A: 2; B: 3
二叉树的遍历
二叉树的遍历是指按照一定的顺序访问二叉树中的每个节点。常见的二叉树遍历方法有以下几种：
- 前序遍历（Pre-order Traversal）：访问根节点，然后递归访问左子树，最后递归访问右子树。前序遍历的顺序是：根 -> 左 -> 右 (NLR)；
- 中序遍历（In-order Traversal）：递归访问左子树，然后访问根节点，最后递归访问右子树。中序遍历的顺序是：左 -> 根 -> 右 (LNR)；
- 后序遍历（Post-order Traversal）：递归访问左子树，然后递归访问右子树，最后访问根节点。后序遍历的顺序是：左 -> 右 -> 根 (LRN)；
- 层序遍历（Level-order Traversal）：按层次从上到下、从左到右访问每个节点。层序遍历通常使用队列实现。
前序遍历
我们以前序遍历为例，由于前序遍历的顺序是根 -> 左 -> 右，也就是说，对于二叉树中的每个节点，我们获取到它的引用后，首先访问它的值，然后访问它的左子节点，最后访问它的右子节点。
试想一下，某个节点在获取到它的值后，就去访问了它的左子节点。假设我们现在就处于这个左子节点，是不是也要先获取它的值，然后接下来又要开始访问这个左子节点的左子节点？
上图展示了前文描述的这个过程。当读取到根节点的值 1 后，我们开始访问它的左子节点。对于左子节点 2，我们同样需要先获取它的值，然后访问它的左子节点 4。对于左子节点 4，我们同样需要先获取它的值，然后访问它的左子节点。但是节点 4 没有左子节点，所以没法继续访问左子节点了。
既然节点 4 没有子节点，那么对于节点 4 来说，无法向左、右子节点进行访问，就相当于已经完成了向左或向右走的过程。
想象一下，现在有一支部队正在行军。他们被委派以走遍所有的营地。每到一个营地就先向总部报点，紧接着往左边的岔路走，最后以这个营地为基准再往右边的岔路走。当走到 4 号营地后，司令问侦察兵：“我们如果往左边岔路走的，接下来会抵达哪个营地？”侦察兵却指着 4 号营地上的小地图说：“报告司令，往左边岔路走的话，走不到任何营地，因为左边岔路的目的地写了个‘空’。”于是司令说：“好吧，那走不了就相当于往左探明营地的任务已经完成了，那往右边走呢？”侦察兵又说：“报告司令，右边岔路目的地也是空的！”此时，部队就只能报告：“现在我们处于 4 号营地，我们遵循着‘每到一个营地就先向总部报点，紧接着往左边的岔路走，最后以这个营地为基准再往右边的岔路走’的命令，如今左右已经无法继续走下去，只得返回 2 号营地！”
我们在 2 号营地放一只眼睛进行观察，不难发现，当部队从 2 号营地去往 4 号营地后，是不是相当于已完成对 2 号营地的报点，但是还在执行“往左边的岔路走”的任务？很快，部队因为无路可走返回到 2 号营地后，完成了“往左边的岔路走”的任务，但是不是还要继续执行“以这个营地为基准再往右边的岔路走”的任务？这样的话，部队就会往 2 号营地的右边岔路走，去往 5 号营地。
按照这样一个逻辑，接下来的故事就不难想象了。部队在 5 号营地报点后，也发现无路可走，只得返回到 2 号营地。但对于 2 号营地来说，部队已经完成了对它的报点、往左走和往右走的任务。既然部队在 2 号营地已经完成了所有任务，那么就可以返回到 1 号营地了。自然对于 1 号营地来说，部队也已经完成了对它的报点、往左走的任务。接下来，部队就会往 1 号营地的右边岔路走，也就是前往 3 号营地。不断递推，就可以将所有的营地都走遍。
其中，蓝线代表着“去”的过程，红线代表着“回”的过程。
不难发现，对于每个节点（营地），都有“报点”、“往左走”和“往右走”三个步骤，都是非常机械式的过程。而且在访问时，下一个节点没结束所有任务之前，上一个节点的“往左走”/“往右走”任务都不会结束。上述三个步骤的过程可以以函数的形式来表达，但是“上一个节点的“往左走”/“往右走”任务都不会结束”就有点类似于一个函数中套着另一个函数的调用，当函数调用没完成时，外层函数的调用就不会结束的感觉。而且还是层层嵌套，从根节点一直到最左端的叶子节点。这让我们想到了什么？没错，就是递归：
template <typename T>
void preOrder(BinaryTree<T>* tree)
{
if (tree != nullptr)
{
cout << "[" << tree->value << "] " << endl;
preOrder(tree->leftChild);
preOrder(tree->rightChild);
}
}
当传入一颗二叉树的（根）节点指针时，preOrder() 函数将会按照前序遍历的顺序访问每个节点，输出节点的值并递归地访问左子节点和右子节点。在 main() 函数中，我们可以调用 preOrder() 函数来测试先前行军案例中对应二叉树的前序遍历的结果：
int main(int argc, char* argv[])
{
// 初始化节点
BinaryTree<int>* root = createBinaryTreeNode(1);
BinaryTree<int>* a = createBinaryTreeNode(2);
BinaryTree<int>* b = createBinaryTreeNode(3);
BinaryTree<int>* d = createBinaryTreeNode(4);
BinaryTree<int>* e = createBinaryTreeNode(5);
BinaryTree<int>* f = createBinaryTreeNode(6);
// 为不同节点指定左、右孩子节点
root->leftChild = a;
root->rightChild = b;
a->leftChild = d;
a->rightChild = e;
b->leftChild = f;
// 调用 preOrder 函数来进行前序遍历
preOrder(root);
return 0;
}
编译并运行上述代码，输出结果如下：
[1]
[2]
[4]
[5]
[3]
[6]
看，是不是和先前画图推演的结果一致~？
（注：由于在为 preOrder() 函数传递 root 变量时，root 变量的类型是 BinaryTree<int>*，因此无需为 preOrder() 函数指定泛型参数 int，编译器可以自动推导出 T 的类型。）
中序遍历与后序遍历
中序遍历与后序遍历的实现与前序遍历类似，只是访问节点的顺序不同。我们可以像实现前序遍历的 preOrder() 函数那样，只需稍作修改，就可以实现中序遍历和后序遍历。
对于中序遍历，访问顺序是左 -> 根 -> 右，也就是先“往左走”，然后“报点”，最后“往右走”：
template <typename T>
void inOrder(BinaryTree<T>* tree)
{
if (tree != nullptr)
{
inOrder(tree->leftChild);
cout << "[" << tree->value << "] " << endl;
inOrder(tree->rightChild);
}
}
对于后序遍历，访问顺序是左 -> 右 -> 根，也就是先“往左走”，然后“往右走”，最后“报点”：
template <typename T>
void postOrder(BinaryTree<T>* tree)
{
if (tree != nullptr)
{
postOrder(tree->leftChild);
postOrder(tree->rightChild);
cout << "[" << tree->value << "] " << endl;
}
}
同样进行测试，对于中序遍历和后序遍历，分别期望输出的结果为：
# 中序遍历
[4]
[2]
[5]
[1]
[6]
[3]
# 后序遍历
[4]
[5]
[2]
[6]
[3]
[1]
在 main() 函数中，分别调用 inOrder() 和 postOrder() 函数来测试中序遍历和后序遍历的结果：
看，是不是也和预期的结果一致~
层序遍历
层序遍历的实现与前序、中序和后序遍历不同。层序遍历需要使用队列来实现，因为它需要按层次从左到右顺序访问/输出每个节点。
如何进行遍历呢？试想一下，如果我们可以将每一层的节点都放入一个队列中，那么就可以从队列中依次取出节点进行访问，满足层序遍历的规则。那是不是可以先把节点放入队列中，然后从队列中取出，读取它的值并看看它有没有左右孩子。如果有，就将左孩子放入队列中，再将右孩子放入队列中，然后再依次出队，在出队时访问节点的值，然后继续看看它有没有左右孩子，直到队列为空为止；如果没有左右孩子，就直接出队，继续出队下一个节点，直到队列为空为止。
对于队列，我们可以使用 std::queue 来实现，笔者已经事先包含了队列相关的头文件（即 #include <queue>）。下面是层序遍历的实现代码：
template <typename T>
void levelOrder(BinaryTree<T>* tree)
{
// 初始化一个队列
queue<BinaryTree<T>*> bTreeQueue;
// 将当前节点入队
bTreeQueue.push(tree);
// 若队列不为空，则说明这一层还有节点
while (bTreeQueue.size() > 0)
{
// 出队队首元素，并输出该节点的值
BinaryTree<T>* currentFront = bTreeQueue.front();
bTreeQueue.pop();
cout << "[" << currentFront->value << "] " << endl;
if (currentFront->leftChild != nullptr)
{
// 将左孩子节点入队
bTreeQueue.push(currentFront->leftChild);
}
if (currentFront->rightChild != nullptr)
{
// 将右孩子节点入队
bTreeQueue.push(currentFront->rightChild);
}
}
}
显然，我们预期的层序遍历结果是：
[1]
[2]
[3]
[4]
[5]
[6]
在 main() 函数中，调用 levelOrder() 函数来测试层序遍历的结果：
非常好，[1..6] 的运行结果也完全符合预期。
至此，我们已经掌握并实现了二叉树的基本结构和常见的遍历方法。接下来，我们将继续探索二叉树的更多变种与特性，并实现一些更复杂的操作，如删除节点、查找节点等。
总结
本主题将分为三节内容，前两节为二叉树的各类基本操作及实现，最后一节为二叉树的简单应用与考点结论。在本文中，我们介绍了二叉树的基本概念、术语和常见种类，并使用 C++ 实现了二叉树节点的定义和基本的遍历方法。我们实现了前序遍历、中序遍历、后序遍历和层序遍历，并通过示例代码验证了这些遍历方法的正确性。本文仅仅是对二叉树的初步探索，将二叉树的初等操作和遍历方法进行了阐述。接下来，我们将继续深入探索二叉树的更多特性和操作，如线索二叉树的构建，节点的插入、删除和查找等操作。
如果您有任何想要了解或分享的内容，欢迎在评论区留言讨论！