如何画一棵漂亮的二叉树

前言

不知道你有没有找过一些工具来画数据结构的图，我反正是找了不少。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命令了。

如何画二叉树

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

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 下载：

// 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);
  }
}