前言
如果我们需要观察程序运行过程中，某一个变量、某一个序列的变化情况，你可以在修改的地方打断点 debug，或者直接在需要的地方输出就行了。
但是对于一些树形结构，我们不好将其直观地呈现出来，常常只是输出每一个结点的值，但是这就丢失了结点之间的连边情况。有时候不得不手动画图。
所以我们经常累死。
于是，为了让我们活着，我想到了一种轻量级的，在终端直观呈现树形结构的方法。
正文
经典例子
回顾如下场景：
- Windows 下命令行中，我们使用
tree来观察目录结构。
比如，在某一目录下，使用 tree /A /F 的输出如下：
+---.vscode | launch.json | +---blog-prettier | LICENSE | README.md | +---web server | | checkstatues.log | | client.html | | data.txt | | gen-key.py | | main_service.log | | script-obfsed.js | | test.html | | | ---fetch-new-url | | README.md | | | ---docs | test | ---test a.html b.html index.html script.js style.css 这种经典的方法显然可以运用到我们的调试中。
分析
二叉树
我们不妨来考虑简单的二叉树，例如线段树、Treap、Splay 等平衡树。
我们考虑一种最简单的递归过程，仅在参数中传递输出的前缀。简单码出以下代码：
void output(int x, string pre) { cout << pre << "-" << x << ": " << tr[x].val << endl; if (!x) return; output(tr[x].son[1], pre + " |"); output(tr[x].son[0], pre + " |"); } void output() { output(root, ">"); } 这里先输出再 return 是为了让输出的二叉树更好看，不然遇到一个孩子不知道是左儿子还是右儿子。
将右儿子作为第一个儿子输出，是为了符合二叉查找树。
可能的输出：一棵不断插入的 Splay
>-1: 1 > |-0: 0 > |-0: 0 >-2: 1 > |-1: 1 > | |-0: 0 > | |-0: 0 > |-0: 0 >-3: 4 > |-0: 0 > |-1: 1 > | |-0: 0 > | |-2: 1 > | | |-0: 0 > | | |-0: 0 >-4: 5 > |-0: 0 > |-3: 4 > | |-0: 0 > | |-1: 1 > | | |-0: 0 > | | |-2: 1 > | | | |-0: 0 > | | | |-0: 0 >-5: 1 > |-3: 4 > | |-4: 5 > | | |-0: 0 > | | |-0: 0 > | |-2: 1 > | | |-1: 1 > | | | |-0: 0 > | | | |-0: 0 > | | |-0: 0 > |-0: 0 >-6: 4 > |-3: 4 > | |-4: 5 > | | |-0: 0 > | | |-0: 0 > | |-0: 0 > |-5: 1 > | |-1: 1 > | | |-0: 0 > | | |-2: 1 > | | | |-0: 0 > | | | |-0: 0 > | |-0: 0 这对于考场上调试来说已经足够了，仅需将头逆时针旋转 (45^circ) 就能看到一棵完美的二叉树了。你可以在每个结点之后输出更多的信息。
但是，我们怎样达到更完美的效果呢，比如第二个孩子之前不输出树杈、第二个孩子后输出空行（多个第二个孩子仅输出一个空行）等等。
我们仅需多记录是否是第一个孩子即可。
void output(int x, string pre, bool firstSon) { cout << pre << (firstSon ? "+" : "\") << "---" << x << ": " << tr[x].val << endl; if (!x) return; pre += firstSon ? "|" : " "; output(tr[x].son[1], pre + " ", true); output(tr[x].son[0], pre + " ", false); if (firstSon) cout << pre << endl; } void output() { output(root, "", false); } 效果见文末。
多叉树
多叉树就只能是 LCT 了吧，还有什么扭曲的树你必须要打印出来的？
虽然好像打印出来还是不方便调试……
我们加以改进，由于有了虚实链之分，我们在空节点不直接 return，而是输出一条边。然后把是否是第一个孩子，变成是否是最后一个孩子。
代码：
vector<int> edge[N]; void output(int x, string pre, bool lastSon, bool real) { cout << pre << (!lastSon ? "+" : "\") << "---"; if (x) cout << x << ": " << tr[x].val << endl; else cout << "null" << endl; pre += !lastSon ? (real ? "|" : "`") : " "; if (x && (tr[x].son[0] || tr[x].son[1] || edge[x].size())) { pushdown(x); output(tr[x].son[1], pre + " ", false, true); output(tr[x].son[0], pre + " ", edge[x].empty(), false); for (int y : edge[x]) output(y, pre + " ", y == edge[x].back(), false); } if (!lastSon) cout << pre << endl; } void output(int n) { for (int i = 1; i <= n; ++i) edge[i].clear(); for (int i = 1; i <= n; ++i) if (isRoot(i)) edge[tr[i].fa].emplace_back(i); cout << "==== LCT forest ====" << endl; for (int i = 1; i <= n; ++i) if (!tr[i].fa) output(i, "", true, false); cout << "====================" << endl; } 效果见文末。
代码
二叉树
void output(int x, string pre, bool firstSon) { cout << pre << (firstSon ? "+" : "\") << "---" << x << ": " << tr[x].val << endl; if (!x) return; pre += firstSon ? "|" : " "; output(tr[x].son[1], pre + " ", true); output(tr[x].son[0], pre + " ", false); if (firstSon) cout << pre << endl; } void output() { output(root, "", false); } 多叉树 LCT
vector<int> edge[N]; void output(int x, string pre, bool lastSon, bool real) { cout << pre << (!lastSon ? "+" : "\") << "---"; if (x) cout << x << ": " << tr[x].val << endl; else cout << "null" << endl; pre += !lastSon ? (real ? "|" : "`") : " "; if (x && (tr[x].son[0] || tr[x].son[1] || edge[x].size())) { pushdown(x); output(tr[x].son[1], pre + " ", false, true); output(tr[x].son[0], pre + " ", edge[x].empty(), false); for (int y : edge[x]) output(y, pre + " ", y == edge[x].back(), false); } if (!lastSon) cout << pre << endl; } void output(int n) { for (int i = 1; i <= n; ++i) edge[i].clear(); for (int i = 1; i <= n; ++i) if (isRoot(i)) edge[tr[i].fa].emplace_back(i); cout << "==== LCT forest ====" << endl; for (int i = 1; i <= n; ++i) if (!tr[i].fa) output(i, "", true, false); cout << "====================" << endl; } 输出效果
可能的输出：一棵不断插入的 Splay
---1: 1 +---0: 0 ---0: 0 ---2: 1 +---1: 1 | +---0: 0 | ---0: 0 | ---0: 0 ---3: 4 +---0: 0 ---1: 1 +---0: 0 ---2: 1 +---0: 0 ---0: 0 ---4: 5 +---0: 0 ---3: 4 +---0: 0 ---1: 1 +---0: 0 ---2: 1 +---0: 0 ---0: 0 ---5: 1 +---3: 4 | +---4: 5 | | +---0: 0 | | ---0: 0 | | | ---2: 1 | +---1: 1 | | +---0: 0 | | ---0: 0 | | | ---0: 0 | ---0: 0 ---6: 4 +---3: 4 | +---4: 5 | | +---0: 0 | | ---0: 0 | | | ---0: 0 | ---5: 1 +---1: 1 | +---0: 0 | ---2: 1 | +---0: 0 | ---0: 0 | ---0: 0 可能的输出：一棵带有左右边界的不断插入的 Treap
---2: inf +---0: 0 ---1: -inf +---3: 1 | +---0: 0 | ---0: 0 | ---0: 0 ---2: inf +---0: 0 ---1: -inf +---3: 1 | +---0: 0 | ---0: 0 | ---0: 0 ---2: inf +---0: 0 ---1: -inf +---3: 1 | +---4: 4 | | +---0: 0 | | ---0: 0 | | | ---0: 0 | ---0: 0 ---2: inf +---0: 0 ---1: -inf +---3: 1 | +---5: 5 | | +---0: 0 | | ---4: 4 | | +---0: 0 | | ---0: 0 | | | ---0: 0 | ---0: 0 ---2: inf +---0: 0 ---1: -inf +---3: 1 | +---5: 5 | | +---0: 0 | | ---4: 4 | | +---0: 0 | | ---0: 0 | | | ---0: 0 | ---0: 0 ---2: inf +---0: 0 ---1: -inf +---3: 1 | +---5: 5 | | +---0: 0 | | ---4: 4 | | +---0: 0 | | ---0: 0 | | | ---0: 0 | ---0: 0 可能的输出：一棵不断插入的无旋 Treap
---1: 1 +---0: 0 ---0: 0 ---1: 1 +---0: 0 ---2: 1 +---0: 0 ---0: 0 ---3: 4 +---0: 0 ---1: 1 +---0: 0 ---2: 1 +---0: 0 ---0: 0 ---3: 4 +---4: 5 | +---0: 0 | ---0: 0 | ---1: 1 +---0: 0 ---2: 1 +---0: 0 ---0: 0 ---5: 1 +---3: 4 | +---4: 5 | | +---0: 0 | | ---0: 0 | | | ---1: 1 | +---0: 0 | ---2: 1 | +---0: 0 | ---0: 0 | ---0: 0 ---5: 1 +---6: 4 | +---3: 4 | | +---4: 5 | | | +---0: 0 | | | ---0: 0 | | | | | ---0: 0 | | | ---1: 1 | +---0: 0 | ---2: 1 | +---0: 0 | ---0: 0 | ---0: 0 可能的输出：一棵动态开点线段树
---[1, 5]: 1 +---[1, 3]: 0 ---[4, 5]: 1 +---[4, 4]: 0 ---[5, 5]: 1 ---[1, 5]: 6 +---[1, 3]: 0 ---[4, 5]: 6 +---[4, 4]: 0 ---[5, 5]: 6 ---[1, 5]: 10 +---[1, 3]: 0 ---[4, 5]: 10 +---[4, 4]: 4 ---[5, 5]: 6 ---[1, 5]: 12 +---[1, 3]: 2 | +---[1, 2]: 0 | ---[3, 3]: 2 | ---[4, 5]: 10 +---[4, 4]: 4 ---[5, 5]: 6 ---[1, 5]: 15 +---[1, 3]: 5 | +---[1, 2]: 3 (with lazy = 3) | | +---[1, 1]: 0 | | ---[2, 2]: 0 | | | ---[3, 3]: 2 | ---[4, 5]: 10 +---[4, 4]: 4 ---[5, 5]: 6 ---[1, 5]: 15 +---[1, 3]: 5 | +---[1, 2]: 3 (with lazy = 3) | | +---[1, 1]: 0 | | ---[2, 2]: 0 | | | ---[3, 3]: 2 | ---[4, 5]: 10 +---[4, 4]: 4 ---[5, 5]: 6 ---[1, 5]: 19 +---[1, 3]: 5 | +---[1, 2]: 3 (with lazy = 3) | | +---[1, 1]: 0 | | ---[2, 2]: 0 | | | ---[3, 3]: 2 | ---[4, 5]: 14 +---[4, 4]: 6 ---[5, 5]: 8 ---[1, 5]: 19 +---[1, 3]: 5 | +---[1, 2]: 3 (with lazy = 3) | | +---[1, 1]: 0 | | ---[2, 2]: 0 | | | ---[3, 3]: 2 | ---[4, 5]: 14 +---[4, 4]: 6 ---[5, 5]: 8 ---[1, 5]: 24 (with lazy = 1) +---[1, 3]: 5 | +---[1, 2]: 3 (with lazy = 3) | | +---[1, 1]: 0 | | ---[2, 2]: 0 | | | ---[3, 3]: 2 | ---[4, 5]: 14 +---[4, 4]: 6 ---[5, 5]: 8 ---[1, 5]: 24 (with lazy = 1) +---[1, 3]: 5 | +---[1, 2]: 3 (with lazy = 3) | | +---[1, 1]: 0 | | ---[2, 2]: 0 | | | ---[3, 3]: 2 | ---[4, 5]: 14 +---[4, 4]: 6 ---[5, 5]: 8 可能的输出：一棵树状数组
这玩意你还要调试？
可能的输出：左偏树森林
==== 左偏树 1 ==== ---5: <4, 2> +---3: <4, 3> | +---4: <5, 2> | | +---0: <0, 0> | | ---7: <9, 4> | | +---0: <0, 0> | | ---0: <0, 0> | | | ---0: <0, 0> | ---0: <0, 0> ==== 左偏树 2 ==== ---1: <3, 3> +---6: <8, 4> | +---0: <0, 0> | ---2: <9, 3> | +---0: <0, 0> | ---0: <0, 0> | ---0: <0, 0> ==== 左偏树 1 ==== ---5: <4, 2> +---3: <4, 3> | +---4: <5, 2> | | +---0: <0, 0> | | ---7: <9, 4> | | +---0: <0, 0> | | ---0: <0, 0> | | | ---0: <0, 0> | ---1: <5, 3> +---6: <8, 4> | +---0: <0, 0> | ---2: <9, 3> | +---0: <0, 0> | ---0: <0, 0> | ---0: <0, 0> ==== 左偏树 1 ==== ---3: <4, 3> +---4: <5, 2> | +---0: <0, 0> | ---7: <9, 4> | +---0: <0, 0> | ---0: <0, 0> | ---1: <5, 3> +---6: <8, 4> | +---0: <0, 0> | ---2: <9, 3> | +---0: <0, 0> | ---0: <0, 0> | ---0: <0, 0> ==== 左偏树 1 ==== ---4: <5, 2> +---1: <5, 3> | +---6: <10, 4> | | +---0: <0, 0> | | ---2: <9, 3> | | +---0: <0, 0> | | ---0: <0, 0> | | | ---7: <11, 4> | +---0: <0, 0> | ---0: <0, 0> | ---0: <0, 0> ==== 左偏树 1 ==== ---1: <5, 3> +---6: <10, 4> | +---0: <0, 0> | ---2: <9, 3> | +---0: <0, 0> | ---0: <0, 0> | ---7: <11, 4> +---0: <0, 0> ---0: <0, 0> ==== 左偏树 1 ==== ---6: <10, 4> +---2: <11, 3> | +---0: <0, 0> | ---7: <11, 4> | +---0: <0, 0> | ---0: <0, 0> | ---0: <0, 0> ==== 左偏树 1 ==== ---2: <11, 3> +---0: <0, 0> ---7: <11, 4> +---0: <0, 0> ---0: <0, 0> ==== 左偏树 1 ==== ---7: <11, 4> +---0: <0, 0> ---0: <0, 0> ==== 左偏树 1 ==== ---0: <0, 0> 可能的输出：Link Cut Tree
==== LCT forest ==== ---1: 114 ---2: 514 ---3: 19 ---4: 19 ---5: 810 ==================== link 1 and 2 success ==== LCT forest ==== ---2: 514 +---null | +---null ` ---1: 114 ---3: 19 ---4: 19 ---5: 810 ==================== cut 1 and 2 success ==== LCT forest ==== ---1: 114 ---2: 514 ---3: 19 ---4: 19 ---5: 810 ==================== link 1 and 2 success ==== LCT forest ==== ---2: 514 +---null | +---null ` ---1: 114 ---3: 19 ---4: 19 ---5: 810 ==================== link 2 and 3 success ==== LCT forest ==== ---3: 19 +---null | +---null ` ---2: 514 +---null | +---null ` ---1: 114 ---4: 19 ---5: 810 ==================== cut 1 and 3 failed ==== LCT forest ==== ---1: 114 +---2: 514 | +---3: 19 | | | ---null | ---null ---4: 19 ---5: 810 ==================== link 1 and 3 failed ==== LCT forest ==== ---1: 114 +---3: 19 | +---null | | | ---2: 514 | ---null ---4: 19 ---5: 810 ==================== link 4 and 5 success ==== LCT forest ==== ---1: 114 +---3: 19 | +---null | | | ---2: 514 | ---null ---5: 810 +---null | +---null ` ---4: 19 ==================== link 2 and 5 success ==== LCT forest ==== ---5: 810 +---null | +---null ` +---2: 514 ` +---1: 114 ` | ` +---null ` ` ` ---3: 19 ` ---4: 19 ==================== modify value 5 to 233333 success ==== LCT forest ==== ---5: 233333 +---null | +---null ` +---2: 514 ` +---1: 114 ` | ` +---null ` ` ` ---3: 19 ` ---4: 19 ==================== access 3 success ==== LCT forest ==== ---5: 233333 +---2: 514 | +---3: 19 | | | +---null | ` | ---1: 114 | +---null ` ---4: 19 ==================== split 2 ~ 4 success ==== LCT forest ==== ---4: 19 +---null | ---5: 233333 +---null | ---2: 514 +---null | +---null ` +---1: 114 ` ---3: 19 ==================== split 2 ~ 5 success ==== LCT forest ==== ---5: 233333 +---null | +---2: 514 ` +---null ` | ` +---null ` ` ` +---1: 114 ` ` ` ---3: 19 ` ---4: 19 ==================== 
![[Java] 计算Java对象大小](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/uploads/2025/01/20250109_677ff40ace135.png&w=218&h=124&zc=1)
