使用graphviz绘制二叉树（二）

缺乏、安全感 2022-06-16 10:17 364阅读 0赞

在上一篇博客中《[使用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"];
    }

输出结果是这样的：

![graphviz][graphviz 1]

有没有丑出新境界？？？

于是，我就进行了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

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

![graphviz][graphviz 2]

现在是不是好看多了！

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

[graphviz]: http://blog.csdn.net/theonegis/article/details/71734847
[graphviz 1]: /images/20220616/5dc9aeb972834a68951a944e5839b2b6.png
[GraphViz formatting script for binary trees]: https://gist.github.com/Sciss/2878988
[graphviz 2]: /images/20220616/bb98b1131be44b0ab4e1f0ab25204651.png