前言

如果我们需要观察程序运行过程中，某一个变量、某一个序列的变化情况，你可以在修改的地方打断点 debug，或者直接在需要的地方输出就行了。

但是对于一些树形结构，我们不好将其直观地呈现出来，常常只是输出每一个结点的值，但是这就丢失了结点之间的连边情况。有时候不得不手动画图。

所以我们经常累死。

于是，为了让我们活着，我想到了一种轻量级的，在终端直观呈现树形结构的方法。

正文

经典例子

回顾如下场景：

Windows 下命令行中，我们使用 tree 来观察目录结构。

比如，在某一目录下，使用 tree /A /F 的输出如下：

/* by yours.tools - online tools website : yours.tools/zh/formatpy.html */

+---.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 等平衡树。

我们考虑一种最简单的递归过程，仅在参数中传递输出的前缀。简单码出以下代码：

/* by yours.tools - online tools website : yours.tools/zh/formatpy.html */

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 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 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

====================

本文作者：XuYueming，转载请注明原文链接：https://www.cnblogs.com/XuYueming/p/18656288。

若未作特殊说明，本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。