⽤css 画出⼆叉树,⽤Graphviz 绘制⼀棵漂亮的⼆叉树起因
之前⽤ Rust 写了⼀个 AVL 树的实现，就很⾃然的想把树⽤可视化的图像画出来，在⼀波搜索过后，最后都指向了⼀位叫 Emden Gansner( Graphviz 主要贡献者之⼀) 的⼤佬在 2010 年写的⼀段脚本，原作者是在邮件列表(链接1，链接2)中回复别⼈的问题时提供的这段脚本，由于这个邮件列表原来的存档⽹站已经⽆法访问，现在能搜到的基本上都是别⼈对这段脚本引⽤，⽐如： stackoverflow。不过这个 gvpr 我实在是看不懂，所以我希望能够直接使⽤ dot 来绘制⼆叉树，这样在⽣成图像的时候就只需要使⽤ dot 命令⾏⼯具⽽不需要额外的脚本了。
尝试
但是事情看起来并没有那么简单，假如我们现在有⼀个⽂件 tree.dot：digraph G {
node [shape=circle]
edge [arrowhead=vee]
8 -> 4
4 -> 2
2 -> 1
2 -> 3
4 -> 6
6 -> 5
6 -> 7
8 -> 10
10 -> 9
10 -> 12
12 -> 11
}
直接⽤ dot tree.dot -Tsvg -otree_0.svg ⽣成出来的图像是这样的：
8
410
261357912
11
然后我们可以过⼀遍那位⼤佬的脚本(把脚本保存为 tree.g)：dot tree.dot | gvpr -c -ftree.g | neato -n -Tsvg -otree_1.svg 得到的图像如下：
8
410
26912
135711
看起来效果还⾏，但是 11 这个节点原本应该在左边，却放到了右边，虽然我可以修改 dot ⽂件让节点放到左边去，不过我想要的效果是不依赖这个脚本。
原理
定位左右⼦节点
在左右⼦节点中间添加⼀个虚拟的占位节点，并且使之与⽗节点在同⼀竖直⽅向上。这可以通过为占位节点(node)和边(edge)设置
style=invis 属性，并且给⽗节点和占位节点设置同⼀个 group 来实现。
同时为了更好的控制左右节点之间的间距，可以对全图设置 nodesep=0，然后对占位节点设置 label="", width=0.3，通过修改这⾥的
0.3 来控制左右节点的间距。当然也可以选择为占位节点设置 width=0，然后通过修改全图设置 nodesep 来控制左右节点的间距，分别使⽤两种⽅式设置相同的节点间距所需的数值有⼀个⼤约 2 倍多的⽐例关系。
所以⼀开始的 tree.dot 更新为：digraph G {
graph [nodesep=0.1]
node [shape=circle]
edge [arrowhead=vee]
8 [group=8]
4 [group=4]
8 -> 4
2 [group=2]
4 -> 2
2 -> 1
_2 [group=2, label="", width=0, style=invis]
2 -> _2 [style=invis]
2 -> 3
_4 [group=4, label="", width=0, style=invis]
4 -> _4 [style=invis]
6 [group=6]
4 -> 6
6 -> 5
_6 [group=6, label="", width=0, style=invis]
6 -> _6 [style=invis]
6 -> 7
_8 [group=8, label="", width=0, style=invis]
8 -> _8 [style=invis]
10 [group=10]
8 -> 10
10 -> 9
_10 [group=10, label="", width=0, style=invis]
10 -> _10 [style=invis]
12 [group=12]
10 -> 12
12 -> 11
_12 [group=12, label="", width=0, style=invis]
12 -> _12 [style=invis]
}
所得图像为：
8
410
26 1357912
11
如果我们使所有的占位节点及边可见，得到的图像是：
8
410
26 1357912
11
看起来效果也还⾏，不过仔细看还是会发现⼀点问题，4 这个节点的位置偏右，这棵数节点不够多还不是很明显，但是如果是⼀棵⼤树，这个偏移会⼗分明显以及丑陋。
定位⽗节点
为了解决前⾯的问题，我们可以考虑将 4 所对应的占位节点下移到 3 和 5 中间，不过 10 所对应的占位节点就不需要下移。
整个规则总结起来就是：⼀个节点对应的占位节点应该与该节点的左⼦树的最⼤节点和右⼦树的最⼩节点中距离较近的那⼀个处于同⼀层。如果根据这个规则，占位节点位于紧邻的下⼀层，我们可以不⽤额外设置。
所以最后的 tree.dot ⽂件应该是这样的(注意含 rank=same 的两⾏)：digraph G {
graph [nodesep=0.1]
node [shape=circle]
edge [arrowhead=vee]
8 [group=8]
4 [group=4]
8 -> 4
2 [group=2]
4 -> 2
2 -> 1
_2 [group=2, label="", width=0, style=invis]
2 -> _2 [style=invis]
2 -> 3
_4 [group=4, label="", width=0, style=invis]
4 -> _4 [style=invis]
6 [group=6]
4 -> 6
6 -> 5
_6 [group=6, label="", width=0, style=invis]
6 -> _6 [style=invis]
6 -> 7
{rank=same; _4; 5}
_8 [group=8, label="", width=0, style=invis]
8 -> _8 [style=invis]
10 [group=10]
8 -> 10
好看的css代码10 -> 9
_10 [group=10, label="", width=0, style=invis]
10 -> _10 [style=invis]
12 [group=12]
10 -> 12
12 -> 11
_12 [group=12, label="", width=0, style=invis]
12 -> _12 [style=invis]
{rank=same; _8; 9}
}
最终得到的图像是：
8
410
26 1357912
11
代码实现
我在之前写的 avl_tree 中实现了将树直接导出为这样的 dot ⽂件的函数：pub fn print_dot(tree: &AvlTreeNode) { fn print_node(node: &TreeNode) {
let mut target = None;
let mut distance = 0;
if let Some(x) = &node.left {
let mut left_max = x;
let mut left_distance = 1;
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论