数据结构-二叉树可视化

发表于 分类于 阅读次数： Disqus： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

  • 二叉树可视化,包括 python 源代码,示例等.

  • 更新

    1
    19.03.24 初始
  • 参考资料

    https://blog.csdn.net/hackooo/article/details/10564049
    https://graphviz.readthedocs.io/en/stable/examples.html

导语

  • 之前冗余的各种重复的代码彻底整理一遍,被python的相对路径折腾死了.
  • 原本打算一块写了,但可视化这部分比较独立,拿出来单独一篇.剩下的内容写在2-3树的前日谭里了.
  • 二叉树可视化,目前支持红黑和普通二叉树,调试方便多了..

二叉树可视化

  • 目标

    • 方便导出(后面有制作 gif 的打算)
    • 支持各类图的绘制.(图的一堆算法在计划列表)
    • 跨平台.(win/linux)

  • 方案

    • 尝试了不少直接输出到命令行,终究还是不方便导出,故放弃.
    • 绘图,matplotlib,杀鸡焉用宰牛刀(其实有点复杂,学习曲线有点陡)..故放弃.
    • 直到想起之前遇到的表述图形描述语言 dot ,找到了 Graphviz .

Graphviz

  • Graphviz : 由AT&T实验室启动的开源工具包，用于绘制DOT语言脚本描述的图形.使用非常方便.

  • 最为重要的是 dot + Graphviz 完美的支持了各类图的绘制,表示图的算法时候会简单很多.

  • 安装

    • python中

      1
      pip install graphviz

    • 这里可以在python中使用 Graphviz 的库,输出 dot 文件了,但还不能渲染出图片.需要系统安装 Graphviz

      1
      sudo apt-get install graphviz

dot语言

  • dot 语言是一种文本图形描述语言,一般 dot 文件以 .gv 或是 .dot 结尾.

  • dot的语法非常简单,要求也并不严格,注释格式等与c语言相同.

  • 这里仅提及部分语法,完整请参考 Dot中文版教程.

  • 这里二叉树的绘制参考

    https://blog.csdn.net/hackooo/article/details/10564049

  • 示例

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    /*digraph 代表有向图 */
    digraph tree {
      /*node的属性设置,全局 可单个覆盖*/
      /*默认 底色:  黑     字体颜色:  白    节点形状: 矩形 类型: 充满*/
      node [color=black fontcolor=white shape=record style=filled]
      /*9 节点   占位  占位 显示 占位*/
      9 [label="<f0> |<f1> 9|<f2>"]
      5 [label="<f0> |<f1> 5|<f2>"]
      /*连接(箭头) sw即 9:f0的左下角 */
      9:f0:sw -> 5:f1
      /*颜色变为红色*/
      18 [label="<f0> |<f1> 18|<f2>" color=red]
      /*连接(箭头) se即 9:f2的右下角 */
      9:f2:se -> 18:f1
    }

  • 渲染后的图像
    tree

可视化

  • 这里要在 python 代码中生成上面的 dot 文本,实际上也非常简单.

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #!/usr/bin/python3
    from graphviz import Digraph, nohtml

    if __name__ == "__main__":
        dot = Digraph(
            name='tree',
            comment='Tree',
            node_attr={
                'shape': 'record',
                'style': 'filled',
                'color': 'black',
                'fontcolor': 'white'
            })
        dot.node('9', nohtml('<f0> |<f1> 9|<f2>'))
        dot.node('5', nohtml('<f0> |<f1> 5|<f2>'))
        dot.edge('9:f0:sw', '5:f1')
        dot.node('18', nohtml('<f0> |<f1> 18|<f2>'), color='red')
        dot.edge('9:f2:se', '18:f1')
        print(dot.source)
        # 指定输出的参数.
        dot.render(
            filename=None, directory=None, view=False, cleanup=False, format='png')
        # 只简单看看效果直接
        # dot.view()

模块

  • 这里结合二叉树的先须遍历,写成模块形式.

  • 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #!/usr/bin/python3

    from graphviz import Digraph, nohtml


    class prtree(object):
        def node(self, dot, node):
            if node.color:
                # 红黑
                dot.node(
                    '%s' % (node.key),
                    nohtml('<f0> |<f1> %s|<f2>' % (node.value)),
                    color='%s' % (node.color))
            else:
                # 普通
                dot.node('%s' % (node.key),
                         nohtml('<f0> |<f1> %s|<f2>' % (node.value)))

        def tree(self, dot, root):
            if root:
                self.node(dot, root)
            if root.lchild:
                # 链接左子树
                dot.edge('%s:f0:sw' % (root.key), '%s:f1' % (root.lchild.key))
                self.tree(dot, root.lchild)
            if root.rchild:
                # 链接右子树
                dot.edge('%s:f2:se' % (root.key), '%s:f1' % (root.rchild.key))
                self.tree(dot, root.rchild)

        def dot(self, root):
            dots = Digraph(
                name='terr',
                comment='Tree',
                node_attr={
                    'shape': 'record',
                    'style': 'filled',
                    'color': 'black',  # 默认为黑色
                    'fontcolor': 'white'  # 字体颜色
                })
            self.tree(dots, root)
            return dots

  • 测试(二叉搜索树)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    if __name__ == "__main__":
        d = randoms.dict_int(n=15)

        test = bst()
        for k, v in d.items():
            test.insert(k, v)

        prt = prtree()
        dot = prt.dot(test.root)
        print(dot.source)
        dot.render(
            filename=None, directory=None, view=False, cleanup=False, format='png')

  • 效果

    • tree
    • 二叉树已经很好的表示出来了,这里也能看出来,单纯二叉搜索树,对深度的控制非常差.

结语

  • 写这篇的时候才发现图床要在3月底关闭了,ai,去搬运图片了,2-3树延后…
相关文章