C/C++二叉树可视化

缘起

C++程序中用到二叉树这种数据结构时，为了可以直观分析数据，好就是把二叉树进行可视化显示。不然调试程序的时候挺恼火的，某个二叉树变量需要一层一层展开分析，很不方便，于是想着写个可视化二叉树的工具。

思路

经过在网上查找一下，很多都是用到了graphviz来可视化， 也就是将二叉树转变为dot语言描述的图，然后利用graphviz库将其转为图片。于是本文针对C/C++中的二叉树，写一个自动可视化二叉树的工具。具体用到了两个第三方库：

• graphviz 2.40.1
• OpenCV 2.3.0

具体思路是: 对二叉树进行层次遍历将二叉树转为dot，然后利用graphviz库对其进行布局和渲染，保存临时图片，最后利用OpenCV显示图片。

实现

基于上述描述，以下说明一下具体实现细节。首先是二叉树转dot：二叉树的一个基本结构是，一个节点指向左右节点，如图

按这样，每遍历到一个节点的时候，则在dot中添加一个上述的基本结构，下图为一个小规模二叉树例子，如图

上图可以看到可视化出来并不是很美观，如图中节点33和172,直接由父节点垂直指出来，特别的，节点172无法判断是左节点还是有节点。于是，对二叉树可视化的基本结构进行了调整，如下图所示

即在父节点中间引出一个placeholder占位符，在生成的dot中设置占位符与父节点在同一个group，并且将占位符的节点和边设置属性为style=invis不可见状态。添加了占位符后，dot语言用法详见Drawing graphs with dot,二叉树可视化结果如下图

上图程序生成的dot文本为

digraph graphname { 
    node [shape=box]; 
    edge [arrowhead=vee];
    0 [label="0"];
    1 [label="149" group=1];
    0 -> 1;
    2 [label="", width=0.1, style=invis, group=0];
    0 -> 2 [style=invis];
    3 [label="63" group=3];
    0 -> 3;
    4 [label="126" group=4];
    1 -> 4;
    5 [label="", width=0.1, style=invis, group=1];
    1 -> 5 [style=invis];
    6 [label="20" group=6];
    1 -> 6;
    7 [label="", width=0.1, style=invis, group=3];
    3 -> 7 [style=invis];
    8 [label="191" group=8];
    3 -> 8;
}

生成了dot之后，其保存在一个字符串变量中，利用graphviz库对其进行渲染，如下代码所示，具体用法详见Using Graphviz as a Library

graph_t *g;
GVC_t *gvc;
gvc = gvContext();
g = agmemread(dot_string);
if(g != NULL){
    gvLayout(gvc, g, "dot");
    gvRenderFilename (gvc, g, "png", out_path);
}
gvFreeLayout(gvc, g);
agclose(g);
gvFreeContext(gvc);

结果示例

下面图是程序自动可视化二叉树的结果示例，包括了highlight指定节点的情况，程序源码详见BinTreeView

无highlight示例：

有highlight示例：