Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3233651
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8557
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: LINUX

2013-03-02 15:31:08

    在我前面的一篇博文数据结构之红黑树中,提到了数据结构之可视化的重要性。 因为如果我们能将二叉树可视化,也能提高加快调试,减少bug。原文给出了print_tree函数,会打印二叉树,但是旋转了90度,不优美,不友好。最近学习了下Graphviz这个软件,学了下怎么用这个软件绘制图片,基本解决了二叉树的可视化问题。

    我还是以我的红黑树代码为例子,写测试代码,看下如何将我们插入产生的红黑树可视化。

    我们看下代码:

  1. typedef unsigned long long ULL;


  2. void __tree2dot(struct rbtree_node* node,FILE* stream)
  3. {
  4.     if(node->color == RB_BLACK)
  5.     {
  6.         fprintf(stream,"%llu [shape=box];n",*(ULL*)(node->key));
  7.     }

  8.     if(node->left)
  9.     {
  10.         
  11.         fprintf(stream," %llu -> %llu;n",*(ULL*)(node->key),*(ULL*)(node->left->key));
  12.         __tree2dot(node->left,stream);
  13.     }
  14.     if(node->right)
  15.     {
  16.         fprintf(stream," %llu -> %llu;n",*(ULL*)(node->key),*(ULL*)(node->right->key));
  17.         __tree2dot(node->right,stream);
  18.     }
  19. }
  20. int tree2dot(struct rbtree* tree,char* filename)
  21. {
  22.     assert(tree != NULL && filename != NULL);
  23.     FILE* stream = fopen(filename,"w+");
  24.     if(stream == NULL)
  25.     {
  26.         fprintf(stderr, "open failed n");
  27.         return -1;
  28.     }

  29.     fprintf(stream,"digraph {n");
  30.     __tree2dot(tree->root,stream);


  31.     fprintf(stream,"}n");
  32.     fclose(stream);

  33.     return 0;
  34.     
  35. }
    tree2dot接受一个二叉树和一个文件名作为入参。负责创建文件 关闭文件和填写dot文件有向图的格式头和尾。

    __tree2dot是递归调用,添加父节点到子节点的有向连接。我们因为是红黑树,所以添加了这部分处理红黑结点的代码:

  1.     if(node->color == RB_BLACK)
  2.     {
  3.         fprintf(stream,"%llu [shape=box];n",*(ULL*)(node->key));
  4.     }
这部分代码的作用对于黑节点,采用box类型表示节点,对于红节点,采用默认的椭圆图形。

比较才能看到进步,我们比较下新旧两种方法的输出:

在看下生成的dot文件(Ubuntu下用XDot打开)

下面这种的优越性,一目了然。这个方法目前有个缺点是没有将NULL节点处理,导致421看不出是386左孩子还是右孩子,我们改进下:


  1. void process_null_node(struct rbtree_node* node, int nullcount, FILE* stream)
  2. {
  3.         fprintf(stream, " null%d [shape=hexagon];n", nullcount);
  4.         fprintf(stream, " %llu -> null%d;n",*(ULL*)(node->key), nullcount);
  5. }
  6. void __tree2dot(struct rbtree_node* node,FILE* stream)
  7. {
  8.     static int null_node_cnt = 0;
  9.     if(node->color == RB_BLACK)
  10.     {
  11.         fprintf(stream,"%llu [shape=box];n",*(ULL*)(node->key));
  12.     }

  13.     if(node->left)
  14.     {
  15.         
  16.         fprintf(stream," %llu -> %llu;n",*(ULL*)(node->key),*(ULL*)(node->left->key));
  17.         __tree2dot(node->left,stream);
  18.     }
  19.     else
  20.     {
  21.         process_null_node(node,null_node_cnt++,stream);
  22.     }
  23.     if(node->right)
  24.     {
  25.         fprintf(stream," %llu -> %llu;n",*(ULL*)(node->key),*(ULL*)(node->right->key));
  26.         __tree2dot(node->right,stream);
  27.     }
  28.     else
  29.     {
  30.         process_null_node(node,null_node_cnt++,stream);
  31.     }
  32. }
我们将NULL节点处理成六边形,这样就能完整的看出红黑树的情况了,请看生成的dot文件:


完整的代码在我的github上 ,可以去下面路径去取:

https://github.com/manuscola/rbtree


参考文献:

1 Drawing graphs with dot


阅读(10549) | 评论(2) | 转发(1) |
给主人留下些什么吧!~~

gfree_wind2013-03-12 20:52:24

漂亮!

wjlkoorey2582013-03-07 19:12:13

内力很刚健