二叉树的绘制

目录

一、知乎方法

二、动手实践

DOT 语言

无向图

有向图

绘制二叉树

设置属性

如何绘制优美的二叉树 

一、知乎方法

知乎上的大佬提供了一系列画图的方法，感兴趣的朋友可以自行去看看

用 Graphviz 绘制一棵漂亮的二叉树 - 南浦月

二叉搜索树，AVL树 - VisuAlgo

Graphviz 入门指南 - 知乎

二、动手实践

DOT 语言

DOT 语言是一种图形描述语言。能够以简单的方式描述图形，并且为人和计算机所理解。

无向图

graph graphname {
   a -- b -- c;
   b -- d;
}

有向图

digraph graphname {
    a -> b -> c;
    b -> d;
}

绘制二叉树

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"];
}

digraph G {
    node [shape=circle]
    edge [arrowhead=vee]
    8 -> 4
    4 -> 2
    2 -> 1
    2 -> 3
    4 -> 6
    6 -> 5
    6 -> 7
    8 -> 10
    10 -> 9
    10 -> 12
    12 -> 11
}

设置属性

属性可以设置在节点和边上，用一对 [] 表示，多个属性可以用空格或者 , 隔开。

strict graph {
  // 设置节点属性
  b [shape=box];
  c [shape=triangle];

  // 设置边属性
  a -- b [color=blue];
  a -- c [style=dotted];
}

 完整的属性列表可以参考Graphviz官网Graphviz。

如何绘制优美的二叉树 

我就进行了Google，发现了Github上还有有人做了相关工作的 GraphViz formatting script for binary trees。

有相关博客可以进一步的学习 

用 Graphviz 绘制一棵漂亮的二叉树 - 南浦月

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