如何优雅地画一棵树
前言
不知道你有没有找过一些工具来画数据结构的图，我反正是找了不少。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执行：
$ sudo apt-get install graphviz安装完后就可以直接使用dot命令了。window下还有可视化界面，可以一边编写，一边预览。
如何画二叉树
实际上，它能够画各种各样的数据结构图，后面也会随着数据结构的介绍而不断介绍各种数据结构的画法，本文仅介绍树的画法。
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。然后在命令行执行命令：
$ 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 下载：
// 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);
}
}这样再次执行命令的时候，只要像下面这样的方式使用即可：
$ dot tree.dot | gvpr -c -f binarytree.gvpr | neato -n -Tpng -o tree.png最后得到的图形如下：
凑合的二叉树
增加一个节点后变成下面这样：
还行的二叉树
去掉样式之后变成这样：
漂亮的二叉树
是不是好看很多呢？
总结
本文仅介绍画简单的二叉树图，实际上它的属性非常非常多，可以满足你的绝大部分需求,非常适合自己调教。