logo标签列表

将一棵二叉树侧向打印

pythontreeformatting
16

如何将一棵二叉树横向打印，使输出结果看起来像这样?

   __/a
__/  \b
  \   _/c
   \_/ \d
     \e

（漂亮的 ASCII 艺术欢迎语）

这里有一些代码，它还没有完全正常运行：

def print_tree(tree):
    def emit(node,prefix):
        if "sequence" in node:
            print "%s%s"%(prefix[:-1],node["name"])
        else:
            emit(node["left"],"%s_/ "%prefix.replace("/ "," /")[:-1].replace("_"," "))
            emit(node["right"],"%s \\ "%prefix.replace("\\ "," \\")[:-1])
    emit(tree,"")

它的输出效果如下：

      _/hg19
    _/ \rheMac2
  _/ \mm9
  /\_/bosTau4
  /  \_/canFam2
_/     \pteVam1
 \_/loxAfr3
   \dasNov2

范围蔓延：如果您能传递一个返回任何节点要打印的字符串的函数，那将非常好；这样，我有时可以打印关于非叶节点的信息。因此，是否要打印一个节点的内容取决于作为参数传递的函数。

这是一些JSON格式的测试数据：

{
    "left": {
        "left": {
            "left": {
                "left": {
                    "name": "hg19", 
                    "sequence": 0
                }, 
                "right": {
                    "name": "rheMac2", 
                    "sequence": 1
                }
            }, 
            "right": {
                "name": "mm9", 
                "sequence": 2
            }
        }, 
        "right": {
            "left": {
                "name": "bosTau4", 
                "sequence": 3
            }, 
            "right": {
                "left": {
                    "name": "canFam2", 
                    "sequence": 4
                }, 
                "right": {
                    "name": "pteVam1", 
                    "sequence": 5
                }
            }
        }
    }, 
    "right": {
        "left": {
            "name": "loxAfr3", 
            "sequence": 6
        }, 
        "right": {
            "name": "dasNov2", 
            "sequence": 7
        }
    }
}
3
你尝试过什么？我能想象它涉及计算树的属性（深度、宽度等）、布局计算和生成 ASCII 艺术。 - Simeon Visser
@SimeonVisser 添加了一些有问题的代码。 - Will
1
看到这个让我想到你应该也要跟踪树的深度。我有一些基于你错误代码的原始代码，但它看起来很糟糕。对于每一行，我试图弄清楚它应该有多少额外的空间，但是该行的重建目前只考虑了最低的分支。 - Michael
你考虑过使用Graphviz语言对树进行序列化吗？有许多布局/渲染工具可以理解这种格式。 - jfs
@J.F.Sebastian 我真的很想避免使用外部依赖，尽管我是graphviz的粉丝。 - Will
相关：https://dev59.com/dk7Sa4cB1Zd3GeqP33ty 和 https://dev59.com/LXRA5IYBdhLWcg3w2x2W 以及 http://eli.thegreenplace.net/2009/11/23/visualizing-binary-trees-with-graphviz/ - jfs
4个回答
7
以下是实现通用递归方法的一些代码，这些代码在其他地方有所描述。树的内部表示可以是一个字符串（叶子）或子节点的元组（对）。节点的中间“片段”的内部表示是元组 （above，below，lines），其中 above 和 below 分别代表根节点上方和下方的行数， lines 是每个不带左侧空格的部分行的迭代器。
#!/usr/local/bin/python3.3

from itertools import chain
from random import randint


def leaf(t):
    return isinstance(t, str)

def random(n):
    def extend(t):
        if leaf(t):
            return (t+'l', t+'r')
        else:
            l, r = t
            if randint(0, 1): return (l, extend(r))
            else: return (extend(l), r)
    t = ''
    for _ in range(n-1): t = extend(t)
    return t

def format(t):
    def pad(prefix, spaces, previous):
        return prefix + (' ' * spaces) + previous
    def merge(l, r):
        l_above, l_below, l_lines = l
        r_above, r_below, r_lines = r
        gap = r_below + l_above
        gap_above = l_above
        gap_below = gap - gap_above
        def lines():
            for (i, line) in enumerate(chain(r_lines, l_lines)):
                if i < r_above:
                    yield ' ' + line
                elif i - r_above < gap_above:
                    dash = '_' if i - r_above == gap_above - 1 else ' '
                    if i < r_above + r_below:
                        yield pad(dash + '/', 2 * (i - r_above), line)
                    else:
                        yield pad(dash + '/', 2 * gap_below - 1, line)
                elif i - r_above - gap_above < gap_below:
                    if i < r_above + r_below:
                        yield pad(' \\', 2 * gap_above - 1, line)
                    else:
                        spaces = 2 * (r_above + gap_above + gap_below - i - 1)
                        yield pad(' \\', spaces, line)
                else:
                    yield ' ' + line
        return (r_above + gap_above, gap_below + l_below, lines())
    def descend(left, t):
        if leaf(t):
            if left:
                return (1, 0, [t])
            else:
                return (0, 1, [t])
        else:
            l, r = t
            return merge(descend(True, l), descend(False, r))
    def flatten(t):
        above, below, lines = t
        for (i, line) in enumerate(lines):
            if i < above: yield (' ' * (above - i - 1)) + line
            else: yield (' ' * (i - above)) + line
    return '\n'.join(flatten(descend(True, t)))


if __name__ == '__main__':
    for n in range(1,20,3):
        tree = random(n)
        print(format(tree))

这是一些示例输出：
          _/rrrr
        _/ \_/rrrlr
       / \   \rrrll
     _/   \_/rrlr
    / \     \rrll
   /   \   _/rlrr
  /     \_/ \rlrl
_/        \_/rllr
 \          \_/rlllr
  \           \rllll
   \        _/lrrr
    \     _/ \lrrl
     \   / \_/lrlr
      \_/    \lrll
        \   _/llrr
         \_/ \llrl
           \_/lllr
             \_/llllr
               \lllll

而且还有一个更不对称的例子，它可能表明为什么我不会在左侧加空格，直到最后（通过 flatten）。如果下半部分在左侧填充了一些，那么上臂的一部分就会跨越填充区域。
               _/rrrrr
             _/ \rrrrl
           _/ \rrrl
         _/ \_/rrlr
        / \   \rrll
       /   \_/rlr
      /      \rll
     /        /lrrr
    /       _/  _/lrrlrr
   /       / \_/ \lrrlrl
  /       /    \lrrll
_/      _/     _/lrlrrr
 \     / \   _/ \lrlrrl
  \   /   \_/ \lrlrl
   \_/      \lrll
     \      _/llrrr
      \   _/ \llrrl
       \_/ \llrl
         \lll

这是一个“显而易见”的递归算法 - 关键在于细节。不使用“_”最容易编写，这使得逻辑稍微复杂一些。
也许唯一的“洞察力”是 gap_above = l_above - 这意味着右侧“臂”的长度等于左子树右侧的长度（你需要读几次才能理解）。它使事情相对平衡。请参阅上面的非对称示例。
更详细地了解问题的好方法是修改pad例程以使用字符代替' '，并为每个调用提供不同的字符。然后，您可以明确地看到哪个逻辑生成了哪个空格。从上到下，从上述调用到下面的 A、B、C 和 D，即可得到此结果（显然，当空格量为零时没有字符）：
             _/rrrr
            / \rrrl
          _/B _/rrlrr
         / \_/ \rrlrl
        /AA  \rrll
      _/BBB  _/rlrrr
     / \DD _/ \rlrrl
    /AA \_/ \_/rlrlr
   /AAAA  \C  \rlrll
  /AAAAAA  \_/rllr
_/AAAAAAAA   \rlll
 \DDDDDDDD   _/lrrrr
  \DDDDDD  _/ \lrrrl
   \DDDD  / \lrrl
    \DD _/B _/lrlrr
     \_/ \_/ \lrlrl
       \C  \lrll
        \_/llr
          \lll

这里有更多的解释（尽管树略有不同），请点击这里。
太好了！请链接到博客文章。一个额外的目标是能够控制每个分支使用的破折号字符串，并且它们可以是可变长度的。 - Will
在http://www.acooke.org/cute/Printingbi0.html发布帖子-代码非常相似，但没有“_”并且有更多的注释。通过比较这两个版本，您可以了解如何添加任意字符串。 - andrew cooke
2

创建一个表示结构，包括一个字符串数组和“花瓣”的行号。

rep(leaf) 是 [0, repr(leaf value)]

对于 nonleaf，给定 top = nonleaf.left 和 bottom = nonleaf.right：

如果在 top 的花瓣上方，则用空格填充 rep(top) 的每一行，如果在下方，则在适当的位置用斜杠填充。同样地，如果在 bottom 的花瓣下方，则用空格填充 rep(bottom) 的每一行，如果在上方，则在适当的位置用反斜杠填充。然后，repr(nonleaf) 就是 [top 的高度，填充后的 top 行跟填充后的 bottom 行]。

例如：

rep(a): [0, ["a"]]
rep(b): [0, ["b"]]
rep(ab): [1, ["/"+"a", "\"+"b"]]
rep(c): [0, ["c"]]
rep(d): [0, ["d"]]
rep(cd): [1, ["/"+"c", "\"+"d"]]
rep(e): [0, ["e"]]
rep(cde): [2, [" "+"/c", "/" + "\d", "\" + "e"]]
rep(abcde): [2, [" "+"/a", "/"+"\b", "\ "+" /c", " \" + "/\d", "  " + "\e"]]

请注意，在上方的情况下，内边距的宽度是花瓣下面的行数；在下方的情况下，内边距的宽度与花瓣相对应。因此，在（abcde）情况下，顶部有2行和1个花瓣，因此填充为（2-1==1）一个字符；底部有2个花瓣，因此填充为2个字符。
如果需要，您还可以在（petal-1）行的每个非叶子节点上添加“_”（并在所有其他行上添加额外的空格）。
显然，这些都不是代码（“\”是一个语法错误等待发生），但从这里实现起来应该不会太困难。
0
你需要递归地处理这个问题，并跟踪每个子树的大小，特别是根节点。一个非平衡树很容易看起来像这样：
/
\/
 \/
  \/
   \

现在假设您已经构建了这棵树，当添加父级别时，您需要进行哪些转换才能得到以下结果。

  /
 /\/
/  \/
\   \/
 \   \
  \

关键思想是从叶子开始。它们很简单。然后定义一种方法来聚合两个子树，假设它们具有不同数量的行和子树根节点的不同位置。
这是一种方法，但你是不是有点忽略了难点？ ;) - Will
嗯，我已经给你提供了关键思路：从叶子到根，跟踪大小和子树根的位置。你需要自己找出确切的字符串操作方法。 我没有为你准备好代码。这是我10年前绘制家谱树时通过输出原始PostScript解决的方式。即使我能找到这段代码，对你来说也没什么用处。 - Has QUIT--Anony-Mousse
0

这里有一棵漂亮的侧向树，它在我的项目调试中帮了我很大的忙： http://www.acooke.org/cute/ASCIIDispl0.html

如果你见过VIM NERDtree插件的目录布局，那么结果会类似。

这是我重新实现的二叉树__str__方法：

def __str__(self):
    """Recursive __str__ method of an isomorphic node."""
    # Keep a list of lines
    lines = list()
    lines.append(self.name)
    # Get left and right sub-trees
    l = str(self.left).split('\n')
    r = str(self.right).split('\n')
    # Append first left, then right trees
    for branch in l, r:
        # Suppress Pipe on right branch
        alt = '| ' if branch is l else '  '
        for line in branch:
            # Special prefix for first line (child)
            prefix = '+-' if line is branch[0] else alt
            lines.append(prefix + line)
    # Collapse lines
    return '\n'.join(lines)
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接