使用graphviz绘制二叉树(二)

在上一篇博客中《使用graphviz绘制二叉树》,提到了一些graphviz的简单的用法。可是如果用上一篇文章中介绍的方法绘制二叉树的话,画出来是及其丑陋的,子节点位置摆放不太好看。自己可以动手试试! 比如我编写了一个tree.dot文件:

graph g {
    graph[ordering="out"];
    A--B;
    A--C;
    B--D;
    B--E;
    C--F;
    C--NULL[style="invis"];
    A[shape="circle"];
    B[shape="circle"];
    C[shape="circle"];
    D[shape="circle"];
    E[shape="circle"];
    F[shape="circle"];
    NULL[style="invis"];
}

输出结果是这样的:

有没有丑出新境界???

于是,我就进行了Google,发现了Github上还有有人做了相关工作的 GraphViz formatting script for binary trees。 下载上面链接中的代码文件,然后对自己的原始dot文件执行如下命令: (假设下载的代码文件名称为binarytree.gvpr,自己的dot文件名称为tree.dot,输出文件为tree.png)

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

我们再来看看运行的结果:

现在是不是好看多了!

gvpr是一种叫做graph pattern scanning and processing language的语言,有兴趣的童鞋可以自己Google,我自己是一句都看不懂。 为了方便起见,我把binarytree.gvpr文件的源码贴出来。

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券