c++可视化 横向打印二叉树（连线、规整）
这次其实是之前一片博客的改进版。这次的二叉树我们使用了经典的 string + vector + shared_ptr 组合，从而使二叉树代码更直观，同时也把内存管理交由 STL 负责。同样地，本文也遵守 Google 风格，以供大家参考。
·
这次其实是之前一片博客的改进版。这次的二叉树我们使用了经典的 string + vector + shared_ptr 组合，从而使二叉树代码更直观，同时也把内存管理交由 STL 负责。同样地，本文也遵守 Google 风格，以供大家参考。
效果图
先来看看效果：
二叉树讲解
树类和树节点类声明如下：
class TreeNode {
public:
TreeNode() : children_(2, nullptr) {}
TreeNode(const T &x) : data_(x), children_(2, nullptr) {}
int Show(vector<vector<string>> &pic, int dep) const;
void Insert(const shared_ptr<TreeNode> &data_ptr);
bool Erase(const T &x, shared_ptr<TreeNode> &pre_ptr);
private: // utility
inline shared_ptr<TreeNode> &left() { return children_.at(0); }
inline shared_ptr<TreeNode> &right() { return children_.at(1); }
inline const shared_ptr<TreeNode> &left() const { return children_.at(0); }
inline const shared_ptr<TreeNode> &right() const { return children_.at(1); }
private:
T data_;
vector<shared_ptr<TreeNode>> children_;
};
class Tree {
public:
void Show() const {
vector<vector<string>> ret;
root_->Show(ret, 0);
for (auto p = ret.rbegin(); p != ret.rend(); ++p) {
for (auto &q : *p) cout << q;
puts("");
}
}
void Insert(const T &x) {
if (nullptr == root_)
root_ = make_shared<TreeNode>(x);
else
root_->Insert(make_shared<TreeNode>(x));
}
bool Erase(const T &x) { return root_->Erase(x, root_); }
private:
shared_ptr<TreeNode> root_;
};
Tree 类负责管理树根指针、封装 TreeNode 类接口。主要功能在 TreeNode 类中递归实现。
我们这里只实现了插入和删除，其余查询功能交由大家自行实现。代码如下：
void TreeNode::Insert(const shared_ptr<TreeNode> &data_ptr) {
auto &next_ptr = data_ptr->data_ < data_ ? left() : right();
if (nullptr == next_ptr)
next_ptr = data_ptr;
else
next_ptr->Insert(data_ptr);
}
bool TreeNode::Erase(const T &x, shared_ptr<TreeNode> &pre_ptr) {
if (x != data_) {
auto &next_ptr = x < data_ ? left() : right();
if (nullptr == next_ptr) return false;
return next_ptr->Erase(x, next_ptr);
}
// x == data_
if (nullptr == left() && nullptr == right()) {
pre_ptr = nullptr;
return true;
}
if (nullptr == left() || nullptr == right()) {
pre_ptr = children_.at(nullptr != right());
return true;
}
// both not null
if (nullptr == right()->left()) {
right()->left() = this->left();
pre_ptr = right();
return true;
}
if (nullptr == left()->right()) {
left()->right() = this->right();
pre_ptr = left();
return true;
}
// find the min node in right
auto &min_node_pre = right();
while (nullptr != min_node_pre->left()->left()) min_node_pre = min_node_pre->left();
min_node_pre->left()->left() = this->left();
pre_ptr = this->right();
return true;
}
由于我们并没有加入平衡树高的机制，删除节点我们只是使用最简单的：将左子树插入到右子树的最左子节点处，然后右子树代替原节点。
打印二叉树讲解
重点来了。我们的思路是这样的：
- 节点类中序遍历节点，后续处理图像。
- 处理好相关数据，放入二维 vec 中。二维 vec 第一维度对应打印的一行，第二维对应打印的前缀+信息内容。
- 树类倒序打印 vec
我们先上代码（但是你可以先不看）再讲解：
int TreeNode::Show(vector<vector<string>> &pic, int dep) const {
int start = pic.size(), sl, sr, ret;
int this_string_length = to_string(data_).size();
string line;
for (int i = 0; i < this_string_length; ++i) line += "─";
// gain
if (nullptr != left()) {
sl = left()->Show(pic, dep + 1);
} else {
pic.push_back(vector<string>{"", "null"});
sl = pic.size() - 1;
}
pic.push_back(vector<string>{"", to_string(data_)});
ret = pic.size() - 1;
if (nullptr != right()) {
sr = right()->Show(pic, dep + 1);
} else {
pic.push_back(vector<string>{"", "null"});
sr = pic.size() - 1;
}
// al
for (int i = start; i <= sl - 1; ++i) pic[i][0] = string(this_string_length + 1, ' ') + pic[i][0];
pic[sl][0] = "└" + line + pic[sl][0];
for (int i = sl + 1; i <= sr - 1; ++i) pic[i][0] = "│" + string(this_string_length, ' ') + pic[i][0];
pic[ret][0] = "";
pic[sr][0] = "┌" + line + pic[sr][0];
for (int i = sr + 1; i < pic.size(); ++i) pic[i][0] = string(this_string_length + 1, ' ') + pic[i][0];
return ret;
}
我们再看这张图：
我们先递归处理左子树 98 的信息，然后放入节点 100 的信息，接着递归处理右子树 101 的信息，最后将左右子树和节点连线，并做一些其它更新（一会儿你将看到）。
为了连线正确，我们需要知道左右子树所在行，我们通过递归返回这个信息。那么当前节点所在行则是当前调用的返回值。这就是 sl, sr, ret 三个变量的意义。
然后我们中序遍历，将信息放入 pic。简单地说，递归左子树（不存在则放入 null）；放入当前节点，顺便记录返回值 ret；递归右子树（不存在则放入 null）。
最后便是画线部分了，首先是：
pic[sl][0] = "└" + line + pic[sl][0];
for (int i = sl + 1; i <= sr - 1; ++i) pic[i][0] = "│" + string(this_string_length, ' ') + pic[i][0];
pic[ret][0] = "";
pic[sr][0] = "┌" + line + pic[sr][0];
这是说：当前节点的列画竖线，左右子树所在行画横线，横线长应该是根据当前节点信息长度自适应的。
画完线之后，我们应该考虑一个问题，这个子树[最左侧,左子树根]和[右子树根,子树最右侧]之间的行应该补上相同数量的空格。这便是如下代码的由来：
for (int i = start; i <= sl - 1; ++i) pic[i][0] = string(this_string_length + 1, ' ') + pic[i][0];
pic[sl][0] = "└" + line + pic[sl][0];
for (int i = sl + 1; i <= sr - 1; ++i) pic[i][0] = "│" + string(this_string_length, ' ') + pic[i][0];
pic[ret][0] = "";
pic[sr][0] = "┌" + line + pic[sr][0];
for (int i = sr + 1; i < pic.size(); ++i) pic[i][0] = string(this_string_length + 1, ' ') + pic[i][0];
注意，start 是在函数开始时进行记录的
完整代码
#include <iostream>
#include <memory>
#include <string>
#include <vector>
using namespace std;
using T = int;
class TreeNode {
public:
TreeNode() : children_(2, nullptr) {}
TreeNode(const T &x) : data_(x), children_(2, nullptr) {}
int Show(vector<vector<string>> &pic, int dep) const;
void Insert(const shared_ptr<TreeNode> &data_ptr);
bool Erase(const T &x, shared_ptr<TreeNode> &pre_ptr);
private:
inline shared_ptr<TreeNode> &left() { return children_.at(0); }
inline shared_ptr<TreeNode> &right() { return children_.at(1); }
inline const shared_ptr<TreeNode> &left() const { return children_.at(0); }
inline const shared_ptr<TreeNode> &right() const { return children_.at(1); }
public:
T data_;
vector<shared_ptr<TreeNode>> children_;
};
class Tree {
public:
void Show() const {
vector<vector<string>> ret;
root_->Show(ret, 0);
for (auto p = ret.rbegin(); p != ret.rend(); ++p) {
for (auto &q : *p) cout << q;
puts("");
}
}
void Insert(const T &x) {
if (nullptr == root_)
root_ = make_shared<TreeNode>(x);
else
root_->Insert(make_shared<TreeNode>(x));
}
bool Erase(const T &x) { return root_->Erase(x, root_); }
private:
shared_ptr<TreeNode> root_;
};
int main() {
Tree root;
root.Insert(52);
root.Insert(2);
root.Insert(102);
root.Insert(1);
root.Insert(100);
root.Insert(98);
root.Insert(90);
root.Insert(101);
root.Insert(1024);
root.Show();
}
void TreeNode::Insert(const shared_ptr<TreeNode> &data_ptr) {
auto &next_ptr = data_ptr->data_ < data_ ? left() : right();
if (nullptr == next_ptr)
next_ptr = data_ptr;
else
next_ptr->Insert(data_ptr);
}
int TreeNode::Show(vector<vector<string>> &pic, int dep) const {
int start = pic.size(), sl, sr, ret;
int this_string_length = to_string(data_).size();
string line;
for (int i = 0; i < this_string_length; ++i) line += "─";
// gain
if (nullptr != left()) {
sl = left()->Show(pic, dep + 1);
} else {
pic.push_back(vector<string>{"", "null"});
sl = pic.size() - 1;
}
pic.push_back(vector<string>{"", to_string(data_)});
ret = pic.size() - 1;
if (nullptr != right()) {
sr = right()->Show(pic, dep + 1);
} else {
pic.push_back(vector<string>{"", "null"});
sr = pic.size() - 1;
}
// al
for (int i = start; i <= sl - 1; ++i) pic[i][0] = string(this_string_length + 1, ' ') + pic[i][0];
pic[sl][0] = "└" + line + pic[sl][0];
for (int i = sl + 1; i <= sr - 1; ++i) pic[i][0] = "│" + string(this_string_length, ' ') + pic[i][0];
pic[ret][0] = "";
pic[sr][0] = "┌" + line + pic[sr][0];
for (int i = sr + 1; i < pic.size(); ++i) pic[i][0] = string(this_string_length + 1, ' ') + pic[i][0];
return ret;
}
bool TreeNode::Erase(const T &x, shared_ptr<TreeNode> &pre_ptr) {
if (x != data_) {
auto &next_ptr = x < data_ ? left() : right();
if (nullptr == next_ptr) return false;
return next_ptr->Erase(x, next_ptr);
}
// x == data_
if (nullptr == left() && nullptr == right()) {
pre_ptr = nullptr;
return true;
}
if (nullptr == left() || nullptr == right()) {
pre_ptr = children_.at(nullptr != right());
return true;
}
// both not null
if (nullptr == right()->left()) {
right()->left() = this->left();
pre_ptr = right();
return true;
}
if (nullptr == left()->right()) {
left()->right() = this->right();
pre_ptr = left();
return true;
}
// find the min node in right
auto &min_node_pre = right();
while (nullptr != min_node_pre->left()->left()) min_node_pre = min_node_pre->left();
min_node_pre->left()->left() = this->left();
pre_ptr = this->right();
return true;
}
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)