相干教程：数据结构树教程
那末如今让我们进入正题。
运用智能指针构建二叉树
我们这里所要完成的是一个简朴地模拟了二叉搜刮树的二叉树，供应相符二叉搜刮树的请求的插进去功用其中序遍历。同时我们运用shared_ptr来治理资本。
如今我们只完成insert和ldr两个要领，其他要领的完成并非本文所体贴的内容，不过我们会在后续的文章中逐一引见：
struct BinaryTreeNode: public std::enable_shared_from_this<BinaryTreeNode> {
explicit BinaryTreeNode(const int value = 0)
: value_{value}, left{std::shared_ptr<BinaryTreeNode>{}}, right{std::shared_ptr<BinaryTreeNode>{}}
{}
void insert(const int value)
{
if (value < value_) {
if (left) {
left->insert(value);
} else {
left = std::make_shared<BinaryTreeNode>(value);
}
}
if (value > value_) {
if (right) {
right->insert(value);
} else {
right = std::make_shared<BinaryTreeNode>(value);
}
}
}
// 中序遍历
void ldr()
{
if (left) {
left->ldr();
}
std::cout << value_ << "\n";
if (right) {
right->ldr();
}
}
// 分层打印
void layer_print();
int value_;
// 摆布子节点
std::shared_ptr<BinaryTreeNode> left;
std::shared_ptr<BinaryTreeNode> right;
private:
// 层序遍历
std::vector<std::shared_ptr<BinaryTreeNode>> layer_contents();
};
我们的node对象继续自enable_shared_from_this，一般这不是必需的，然则为了在层序遍用时轻易操纵，我们须要从this组织智能指针，因而这步是必需的。insert会将比root小的元素插进去左子树，比root大的插进去到右子树；ldr则是最为通例的中序遍历，这里完成它是为了以通例体式格局检察tree中的一切元素。
值得注重的是，关于node节点我们最好运用make_shared举行建立，而不是将其初始化为全局/部份对象，否则在层序遍用时会由于shared_ptr的析构进而致使对象被烧毁，从而激发未定义行动。
如今假定我们有一组数据：[3, 1, 0, 2, 5, 4, 6, 7]，将第一个元素作为root，将一切数据插进去我们的树中会获得以下的一棵二叉树：
auto root = std::make_shared<BinaryTreeNode>(3); root->insert(1); root->insert(0); root->insert(2); root->insert(5); root->insert(4); root->insert(6); root->insert(7);
能够看到节点一共分成了四层，如今我们须要逐层打印，该怎么做呢？
层序遍历
实在思绪很简朴，我们采纳广度优先的思绪，先将节点的孩子都打印，然后再去打印子节点的孩子。
以上图为例，我们先打印根节点的值3，然后我们再打印它的一切子节点的值，是1和5，然后是摆布子节点的子节点，以此类推。。。。。。
说起来很简朴，然则代码写起来却会碰到贫苦。我们不能简朴得像中序遍用时那样运用递返来解决题目（事实上能够用革新的递归算法），由于它会直接来到叶子节点处，这不是我们想要的效果。不过没关系，我们能够借助于行列，把子节点行列增加到行列末端，然后从行列开首也就是根节点处遍历，将其子节点增加进行列，随后再对第二个节点做一样的操纵，碰到一行完毕的处所，我们运用nullptr做标记。
先看细致的代码：
std::vector<std::shared_ptr<BinaryTreeNode>>
BinaryTreeNode::layer_contents()
{
std::vector<std::shared_ptr<BinaryTreeNode>> 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;
}
代码自身并不庞杂，主要的是其背地的头脑。
算法图解
假如你第一遍并没有读懂这段代码也没关系，下面我们有请图解上线：
首先是轮回最先时的状况，第一行的内容已肯定了(^代表空指针)：
然后我们从首元素最先遍历，第一个遍历到的是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 << (*iter)->value_ << " ";
} else {
std::cout << "\n";
}
}
}
如你所见，这个要领充足简朴，我们把节点信息保留在分外的容器中是为了轻易做进一步的处置惩罚，假如只是打印的话大可不必这么贫苦，不过简朴一般是有价值的。关于我们的完成来讲，分隔符的存在简化了我们对层级之间的辨别，然则如许会致使糟蹋最少log2(n)+1个vector的存储空间，某些情况下能够引发机能题目，而且经由过程合理得运用计数变量能够防止这些分外的空间糟蹋。固然细致的完成读者能够自身应战一下，道理和我们上面引见的是相似的因而就不在赘述了，也能够参考园内其他的博客文章。
测试
末了让我们看看完全的测试顺序，记着要用make_shared建立root实例：
int main()
{
auto root = std::make_shared<BinaryTreeNode>(3);
root->insert(1);
root->insert(0);
root->insert(2);
root->insert(5);
root->insert(4);
root->insert(6);
root->insert(7);
root->ldr();
std::cout << "\n";
root->layer_print();
}
输出：
能够看到上半部份是中序遍历的效果，下半部份是层序遍历的输出，而且是逐行打印的，不过我们没有做缩进。所以不太雅观。
别的你能够已发现了，我们没有写任何有关资本开释的代码，没错，这就是智能指针的威力，只需注重资本的建立，剩下的事都能够放心得交给智能指针处置惩罚，我们能够把更多的精神集合在算法和功用的完成上。
若有毛病和疑问迎接指出！
以上就是c++ 图解层序遍历和逐层打印智能指针制作的二叉树的细致内容，更多请关注ki4网别的相干文章！
