当我们学习二叉树时，一个常见的练习就是将其“打印”到控制台上，并用字符（如 _ 和 |）来表示树的结构。这看起来像一个简单的先序遍历问题，但它实际上隐藏着一个有趣的布局挑战。
错误的直觉：为什么“边遍历边插列”行不通？
我们最直观的想法可能是：
从根节点 A 开始，把它放在 (0, 0) 位置。
遇到左孩子 B？在 A 的左边插入一列，把 A 往右推，然后把 B 放在 A 的左下方。
遇到 B 的右孩子 D？在 B 的右边插入一列，把 A（和它右侧的所有东西）再往右推，然后把 D 放在 B 的右下方。
这个“自顶向下、动态插入”的思路看起来很自然，但它有一个致命的缺陷：子节点的操作会反向“推挤”它的祖先节点。
就像我们之前推演的，当 B 的子树在不断插入列时，A 的位置会被挤得越来越偏。最终，A 根本不会在它的左右子树 B 和 C 的正中间。你会得到一棵倾斜、错位的树。
正确的算法：“先计算，后绘制”的两遍遍历
要画出一棵“完美”（即父节点永远在子节点中心）的树，我们必须换个思路。
核心思想：在绘制任何一个节点之前，你必须先知道它所有子孙节点的布局。
这意味着我们不能一次遍历就搞定，而需要一个“计算”和“绘制”分离的策略。这个策略的核心是“自底向上”的。
阶段 1：奠基 (中序遍历) - 确定叶子节点与"大列"
布局的真正基础不是根节点，而是叶子节点。是叶子节点的数量和分布，决定了整棵树需要多“宽”。
遍历方式：我们使用中序遍历。为什么？因为中序遍历能保证我们从左到右的顺序访问叶子节点。
分配"大列"：我们设置一个全局的 x 坐标计数器。每当在中序遍历中访问到一个叶子节点时，我们就将当前的 x 坐标分配给它，然后将 x 计数器增加一个固定的“大列”宽度（例如 +4）。
确定 Y 坐标：在遍历的同时，我们根据节点的深度 (depth)，轻松计算出它的 y 坐标（例如 y = depth * 3）。
完成这个阶段后，所有的叶子节点都有了准确的、从左到右排开的 (x, y) 坐标。我们为整棵树的布局打下了“地基”。
阶段 2：汇总 (后序遍历) - 自底向上计算父节点
现在我们有了“地基”（叶子），我们需要“自底向上”地把整栋楼（父节点）盖起来。
遍历方式：我们使用后序遍历。
为什么是后序？因为对于任何一个父节点 N，我们必须先知道它的左孩子 L 的坐标和右孩子 R 的坐标，然后才能计算它自己的坐标。
计算公式：
如果节点有左右两个孩子：node.x = (node.left.x + node.right.x) / 2。
这就是“居中”的秘密！
如果节点只有一个孩子（左或右）：则在孩子 x 坐标的基础上偏移一点（例如 +2 或 -2）来保持树的“分支”感。
完成这个阶段后，树中的每一个节点（无论是叶子还是父节点）都拥有了它在画布上的最终 (x, y) 坐标。
阶段 3：绘制 (任意遍历) - 填充画布
最难的部分已经结束了。现在，我们的树结构（如 Node* root）和它的坐标数据（如 map<Node*, Point>）是完全分离的。
我们只需要最后再遍历一次整棵树（用先序、中序、后序都无所谓），然后：
在 (node.x, node.y) 处画上节点数据 (如 A, B, C…)。
在 (node.y + 1, …) 和 (node.y + 2, …) 处，根据父子节点的坐标画出连接线 _ 和 |。
总结
这个算法的精髓在于分离了布局计算和实际绘制。通过“中序遍历定叶子”和“后序遍历定父节点”，我们采用了一种“自底向上”的策略，完美地解决了“父节点如何居中”的难题。
这里有一个动画来帮你直观的理解这个过程：
二叉树 "大列" 布局动画
展示 "先计算叶子位置 (大列)，再向上推导父节点" 的过程。
准备就绪
C++实现
tree_print.cpp
在新窗口打开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
| //
// Created by 狗带菌 on 2025/11/17.
//
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
Node* left;
Node* right;
char data;
Node() = default;
explicit Node(char c) {
data = c;
left = right = nullptr;
};
};
Node* buildTreeFromPreOrder(string& text) {
while (!text.empty() && text[0] == ' ') {
text.erase(0, 1);
}
if (text.empty()) return nullptr;
char data = text[0];
text.erase(0, 1);
if (data == '#') return nullptr;
Node* root = new Node(data);
root->left = buildTreeFromPreOrder(text);
root->right = buildTreeFromPreOrder(text);
return root;
}
void preOrder(Node* root) {
if (root == nullptr) return;
cout << root->data << " ";
preOrder(root->left);
preOrder(root->right);
}
//为所有叶子节点分配坐标，也确定了整个画布的宽度global_x
void findLeafCoords(Node* node, int depth, int& global_x,
map<Node*, int>& node_x, map<Node*, int>& node_y) {
if (node == nullptr) {
return;
}
node_y[node] = depth * 3;
//中序遍历
findLeafCoords(node->left, depth + 1, global_x, node_x, node_y);
//叶子节点
if (node->left == nullptr && node->right == nullptr) {
node_x[node] = global_x;
global_x += 4;
}
findLeafCoords(node->right, depth + 1, global_x, node_x, node_y);
}
//为所有非叶子节点分配坐标
void findParentCoords(Node* node, map<Node*, int>& node_x) {
if (node == nullptr) {
return;
}
// 后序遍历
findParentCoords(node->left, node_x);
findParentCoords(node->right, node_x);
if (node->left == nullptr && node->right == nullptr) {
return;
}
// 计算父节点的 x 坐标
if (node->left && node->right) {
node_x[node] = (node_x[node->left] + node_x[node->right]) / 2;
}
else if (node->left) {
node_x[node] = node_x[node->left] + 2;
}
else {
node_x[node] = node_x[node->right] - 2;
}
}
void drawOnCanvas(Node* node, vector<vector<string>>& cells,
map<Node*, int>& node_x, map<Node*, int>& node_y) {
if (node == nullptr) {
return;
}
// 从 map 中读取坐标
int x = node_x[node];
int y = node_y[node];
cells[y][x] = string(1, node->data);
if (node->left || node->right) {
cells[y + 1][x] = "|";
}
if (node->left) {
int lx = node_x[node->left];
cells[y + 2][lx] = "|";
for (int i = lx; i < x; ++i) {
cells[y + 1][i] = "_";
}
}
if (node->right) {
int rx = node_x[node->right];
cells[y + 2][rx] = "|";
for (int i = x + 1; i <= rx; ++i) {
cells[y + 1][i] = "_";
}
}
// 递归绘制
drawOnCanvas(node->left, cells, node_x, node_y);
drawOnCanvas(node->right, cells, node_x, node_y);
}
void showTree(Node* root) {
if (root == nullptr) {
cout << "(空树)" << endl;
return;
}
map<Node*, int> node_x;
map<Node*, int> node_y;
int global_x_counter = 0;
findLeafCoords(root, 0, global_x_counter, node_x, node_y);
findParentCoords(root, node_x);
// 计算画布的确切尺寸
int numCols = global_x_counter;
int numRows = 0;
for (auto const& [node, y_coord] : node_y) {
numRows = max(numRows, y_coord);
}
numRows += 3;
if (numCols == 0) return;
// 创建画布
string fillString = " ";
vector<vector<string>> cells(numRows, vector<string>(numCols, fillString));
// 绘制
drawOnCanvas(root, cells, node_x, node_y);
for (int i = 0; i < numRows; ++i) {
for (int j = 0; j < numCols; ++j) {
cout << cells[i][j];
}
cout << endl;
}
}
int main() {
string text;
getline(cin, text);
Node* root = buildTreeFromPreOrder(text);
cout << endl;
showTree(root);
return 0;
}
|