C++ 智能指针和二叉树：图解层序遍历和逐层打印二叉树

作者：apocelipes
链接：https://www.cnblogs.com/apocelipes/p/10758692.html

二叉树是极为常见的数据结构，关于如何遍历其中元素的文章更是数不胜数。

然而大多数文章都是讲解的前序/中序/后序遍历，有关逐层打印元素的文章并不多，已有文章的讲解也较为晦涩读起来不得要领。本文将用形象的图片加上清晰的代码帮助你理解层序遍历的实现，同时我们使用现代c++提供的智能指针来简化树形数据结构的资源管理。

那么现在让我们进入正题。
[h2]使用智能指针构建二叉树[/h2]我们这里所要实现的是一个简单地模拟了二叉搜索树的二叉树，提供符合二叉搜索树的要求的插入功能个中序遍历。同时我们使用shared_ptr来管理资源。

现在我们只实现insert和ldr两个方法，其余方法的实现并不是本文所关心的内容，不过我们会在后续的文章中逐个介绍：

struct BinaryTreeNode: public std::enable_shared_from_this {
explicit BinaryTreeNode(const int value = 0)
: value_{value}, left{std::shared_ptr{}}, right{std::shared_ptr{}}
{}
void insert(const int value)
{
if (value < value_) {
if (left) {
left->insert(value);
} else {
left = std::make_shared(value);
}
}
if (value > value_) {
if (right) {
right->insert(value);
} else {
right = std::make_shared(value);
}
}
}
// 中序遍历
void ldr()
{
if (left) {
left->ldr();
}
std::cout insert(1);
root->insert(0);
root->insert(2);
root->insert(5);
root->insert(4);
root->insert(6);
root->insert(7);可以看到节点一共分成了四层，现在我们需要逐层打印，该怎么做呢？

复制代码

[h1][/h1]

[h2]层序遍历[/h2]其实思路很简单，我们采用广度优先的思路，先将节点的孩子都打印，然后再去打印子节点的孩子。

以上图为例，我们先打印根节点的值3，然后我们再打印它的所有子节点的值，是1和5，然后是左右子节点的子节点，以此类推。。。。。。

说起来很简单，但是代码写起来却会遇到麻烦。我们不能简单得像中序遍历时那样使用递归来解决问题（事实上可以用改进的递归算法），因为它会直接来到叶子节点处，这不是我们想要的结果。不过不要紧，我们可以借助于队列，把子节点队列添加到队列末尾，然后从队列开头也就是根节点处遍历，将其子节点添加进队列，随后再对第二个节点做同样的操作，遇到一行结束的地方，我们使用nullptr做标记。

先看具体的代码：

std::vector
BinaryTreeNode::layer_contents()
{
std::vector nodes;
// 先添加根节点，根节点自己就会占用一行输出，所以添加了作为行分隔符的nullptr
// 因为需要保存this，所以这是我们需要继承enable_shared_from_this是理由
// 同样是因为这里，当返回的结果容器析构时this的智能指针也会析构
// 如果我们使用了局部变量则this的引用计数从1减至0，导致对象被销毁，而使用了make_shared创建的对象引用计数是从2到1，没有问题
nodes.push_back(shared_from_this());
nodes.push_back(nullptr);
// 我们使用index而不是迭代器，是因为添加元素时很可能发生迭代器失效，处理这一问题将会耗费大量精力，而index则无此烦恼
for (int index = 0; index < nodes.size(); ++index) {
if (!nodes[index]) {
// 子节点打印完成或已经遍历到队列末尾
if (index == nodes.size()-1) {
break;
}
nodes.push_back(nullptr); // 添加分隔符
continue;
}
if (nodes[index]->left) { // 将当前节点的子节点都添加进队列
nodes.push_back(nodes[index]->left);
}
if (nodes[index]->right) {
nodes.push_back(nodes[index]->right);
}
}
return nodes;
}

复制代码

代码本身并不复杂，重要的是其背后的思想。
[h2]算法图解[/h2]如果你第一遍并没有读懂这段代码也不要紧，下面我们有请图解上线：

首先是循环开始时的状态，第一行的内容已经确定了(^代表空指针)：

然后我们从首元素开始遍历，第一个遍历到的是root，他有两个孩子，值分别是1和5：

接着索引值+1，这次遍历到的是nullptr，因为不是在队列末尾，所以我们简单添加一个nullptr在队列末尾，这样第二行的节点就都在队列中了：

随后我们开始遍历第二行的节点，将它们的子节点作为第三行的内容放入队列，最后加上一个行分隔符，以此类推：

简单来说，就是通过队列来缓存上一行的所有节点，然后再根据上一行的缓存得到下一行的所有节点，循环往复直到二叉树的最后一层。当然不只是二叉树，其他多叉树的层序遍历也可以用类似的思想实现。

好了，知道了如何获取每一行的内容，我们就能逐行处理节点了：

void BinaryTreeNode::layer_print()
{
auto nodes = layer_contents();
for (auto iter = nodes.begin(); iter != nodes.end(); ++iter) {
// 空指针代表一行结束，这里我们遇到空指针就输出换行符
if (*iter) {
std::cout value_ insert(0);
root->insert(2);
root->insert(5);
root->insert(4);
root->insert(6);
root->insert(7);
root->ldr();
std::cout layer_print();
}

复制代码

输出：

可以看到上半部分是中序遍历的结果，下半部分是层序遍历的输出，而且是逐行打印的，不过我们没有做缩进。所以不太美观。

另外你可能已经发现了，我们没有写任何有关资源释放的代码，没错，这就是智能指针的威力，只要注意资源的创建，剩下的事都可以放心得交给智能指针处理，我们可以把更多的精力集中在算法和功能的实现上。

智能指针和层序遍历的内容到这里就结束了，在下一篇文章中我们还将看到智能指针和二叉树的更多操作。

●编号492，输入编号直达本文

●输入m获取文章目录
C语言与C++编程
分享C/C++技术文章