如何画一棵漂亮的二叉树

前言

不知道你有没有找过一些工具来画数据结构的图,我反正是找了不少。windows下的visio是挺强大的,不过在linux没法使用,当然你非要使用也可以安装wine;亿图也不错,支持画数据结构图,不过是收费的。然而前面这些都不是重点,重点是他们画图都是拖拽类型的,手残党实在把持不住。最后终于发现了一款程序员画图神器-graphviz。《什么是二叉查找树》文中的树图就是用该工具画的.

graphviz简介

Graphviz是开源图形可视化软件。图形可视化是一种将结构信息表示为抽象图和网络图的方法。 它在网络,生物信息学,软件工程,数据库和网页设计,机器学习以及其他技术领域的可视化界面中具有重要的应用。—来自Graphviz官网https://www.graphviz.org/。

实际上它和markdown类似,markdown用纯文本编写文档,而能够转化成格式丰富的html,而graphviz使用dot标记语言来编写,能够被转换成svg,png,jpg等图形格式。甚至可以说,它就是用纯文本来完成画图。

除此之外,它还提供多种语言的api接口,例如,C,python,java,ruby等,也就是说,你可以根据自己的需要通过编写代码来生成你需要的图形。不过文本不准备使用这种方式,而是直接使用dot语言来画我们需要的图。

安装

linux,windows,mac等系统都支持,安装包下载地址:graphviz。具体安装过程就不介绍了。安装完成后,windows下有一个gvedit.exe的程序可以用来编辑预览,但是关键使用的还是dot.exe。而linux执行:

1
$ sudo apt-get install graphviz

安装完后就可以直接使用dot命令了。

如何画二叉树

实际上,它能够画各种各样的数据结构图,后面也会随着数据结构的介绍而不断介绍各种数据结构的画法,本文仅介绍树的画法。

1
2
3
4
5
6
7
8
9
10
digraph binaryTree{
node[shape=circle,color=red,fontcolor=blue,fontsize=10];
root[color=blue,fontcolor=black,fontsize=20];
root->a[style=dotted];
root->b;
a->c;
a->d;
b->e;
b->f;
}

将上面的内容保存在一个文件,并以.dot结尾,例如tree.dot。然后在命令行执行命令:

1
$ dot -Tpng -o tree.png tree.dot

其中-Tpng表明要将该dot文件转换为png格式的图片,当然你也可以转换为svg,jpg等其他格式的图片。-o 后面是输出文件名。最后会在目录下发现下面的图片:

随便一棵树

是不是很简单?

当然在这里有必要对内容进行一些说明。

  • digraph说明这是一个有向图,也就是后面的指向都是有方向的。
  • binaryTree只是起的一个名字。
  • node行可以用来说明节点的属性,本文例子说,表明它的节点形状是圆,边框颜色为红色,字体颜色为蓝色,字体大小20。当然你也可以指定单个节点的属性,例如后面的root节点单独设置。
  • 文中用->来表明节点的指向。而style=dotted表明该箭头会是虚线箭头。
  • 每行以分号结尾。

一棵漂亮的二叉树

但是你有没有发现一个问题,二叉树各个节点分布并不是那么好看,如果再去掉一个节点,会变成下面这样:

歪脖子树

完全没有左右孩子的感觉了对不对?那怎么办呢?所幸的是,有人已经做了一个优化。将下面的内容保存为文件binarytree.gvpr或从这里https://gist.github.com/Sciss/2878988 下载:

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
// from Emden Gansner
// https://mailman.research.att.com/pipermail/graphviz-interest/2010q2/007101.html
// requires GraphViz 2.28.0 (fails with 2.26.3 at least)
BEGIN {
double tw[node_t]; // width of tree rooted at node
double nw[node_t]; // width of node
double xoff[node_t]; // x offset of root from left side of its tree
double sp = 36; // extra space between left and right subtrees
double wd, w, w1, w2;
double x, y, z;
edge_t e1, e2;
node_t n;
}
BEG_G {
$.bb = "";
$tvtype=TV_postfwd; // visit root after all children visited
}
N {
sscanf ($.width, "%f", &w);
w *= 72; // convert inches to points
nw[$] = w;
if ($.outdegree == 0) {
tw[$] = w;
xoff[$] = w/2.0;
}
else if ($.outdegree == 1) {
e1 = fstout($);
w1 = tw[e1.head];
tw[$] = w1 + (sp+w)/2.0;
if (e1.side == "left")
xoff[$] = tw[$] - w/2.0;
else
xoff[$] = w/2.0;
}
else {
e1 = fstout($);
w1 = tw[e1.head];
e2 = nxtout(e1);
w2 = tw[e2.head];
wd = w1 + w2 + sp;
if (w > wd)
wd = w;
tw[$] = wd;
xoff[$] = w1 + sp/2.0;
}
}
BEG_G {
$tvtype=TV_fwd; // visit root first, then children
}
N {
if ($.indegree == 0) {
sscanf ($.pos, "%f,%f", &x, &y);
$.pos = sprintf("0,%f", y);
}
if ($.outdegree == 0) return;
sscanf ($.pos, "%f,%f", &x, &y);
wd = tw[$];
e1 = fstout($);
n = e1.head;
sscanf (n.pos, "%f,%f", &z, &y);
if ($.outdegree == 1) {
if (e1.side == "left")
n.pos = sprintf("%f,%f", x - tw[n] - sp/2.0 + xoff[n], y);
else
n.pos = sprintf("%f,%f", x + sp/2.0 + xoff[n], y);
}
else {
n.pos = sprintf("%f,%f", x - tw[n] - sp/2.0 + xoff[n], y);
e2 = nxtout(e1);
n = e2.head;
sscanf (n.pos, "%f,%f", &z, &y);
n.pos = sprintf("%f,%f", x + sp/2.0 + xoff[n], y);
}
}

这样再次执行命令的时候,只要像下面这样的方式使用即可:

1
$ dot tree.dot | gvpr -c -f binarytree.gvpr | neato -n -Tpng -o tree.png

最后得到的图形如下:

凑合的二叉树

增加一个节点后变成下面这样:

还行的二叉树

去掉样式之后变成这样:
漂亮的二叉树

是不是好看很多呢?

总结

本文仅介绍画简单的二叉树图,实际上它的属性非常非常多,可以满足你的绝大部分需求,非常适合自己调教。

讨论

你有什么好的画图工具?欢迎留言分享。

守望 wechat
关注[编程珠玑]获取更多原创技术文章
出入相友,守望相助!