打印二叉树放在旁边

Question

如何在二叉树的侧面打印出这样的输出呢？在

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

_{（欢迎使用更漂亮的ascii艺术）}

以下是一些不太管用的代码：

^{pr2}$

其输出如下：

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

Scope crawe：如果您可以传入一个函数，该函数将返回要打印的任何节点的字符串；这样，我有时也可以打印有关非离开节点的信息。因此，节点是否有要打印的内容由作为参数传入的函数控制。在

以下是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
        }
    }
}

Answer 1

您需要递归地处理这个问题，并跟踪各个子树的大小。尤其是根在哪里。非平衡树很容易看起来像这样：

/
\/
 \/
  \/
   \

现在假设您已经构建了这个树，在添加父级时，您需要将它转换为以下内容。在

^{2}$

关键是从树叶开始。它们是微不足道的。然后定义一种聚合两个子树的方法，假设它们具有不同的行数和子树根节点的不同位置。在

Answer 2

下面是一些代码，它们实现了别处描述的通用递归方法。树的内部表示是子节点的字符串（叶）或元组（对）。节点中间“片段”的内部表示是元组(above, below, lines)，其中above和{}是根上下的行数，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))

下面是一些输出示例：

^{2}$

还有一个更不对称的例子，也许可以说明为什么我在行尾之前不在左边填充空格（viaflatten）。如果下半身被垫在左边，上臂的一些部分会穿过填充区域。在

               _/rrrrr
             _/ \rrrrl
           _/ \rrrl
         _/ \_/rrlr
        / \   \rrll
       /   \_/rlr
      /      \rll
     /        /lrrr
    /       _/  _/lrrlrr
   /       / \_/ \lrrlrl
  /       /    \lrrll
_/      _/     _/lrlrrr
 \     / \   _/ \lrlrrl
  \   /   \_/ \lrlrl
   \_/      \lrll
     \      _/llrrr
      \   _/ \llrrl
       \_/ \llrl
         \lll

这是一个“显而易见”的递归算法——魔鬼在细节中。没有“u”是最容易写的，这使得逻辑稍微复杂一些。在

也许唯一的“洞察力”是gap_above = l_above-也就是说右“臂”的长度与左子树右侧的长度相同（你需要读几遍）。它使事情相对平衡。请参阅上面的不对称示例。在

更详细地理解事情的一个好方法是修改pad例程，使其接受一个字符而不是{}，并为每个调用指定一个不同的字符。然后你就可以确切地看到哪个逻辑生成了哪个空间。这是使用A.B、C和D从上到下、从上到下调用pad时得到的结果（显然，当空间量为零时没有字符）：

             _/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

这里有更多的解释here（尽管这棵树略有不同）。在

Answer 3

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

rep（leaf）为[0，repr（叶值）]

rep（非叶），给定top = nonleaf.left和bottom = nonleaf.right：

每行rep（顶部）垫空格，如果上面的花瓣，或斜线在适当的位置，如果下面。类似地，在rep（底部）的每一行都填充空格（如果在底部的花瓣之下），或者在上面的适当位置用反斜杠填充。repr（nonleaf）则是[顶部的高度，顶部的填充线，然后是底部的填充线]。在

示例：

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

注意，在上面的情况下，填充的宽度是花瓣下面的行数；在底部情况下，填充的宽度对应于petal。因此，在（abcde）的情况下，顶部有2行，花瓣1，所以填充是（2-1==1）一个字符；底部有花瓣2，所以填充是2个字符。在

如果您愿意，您还可以在第（petal-1）行的每个非叶处添加一个“u”（在所有其他行上添加一个额外的空格）。在

显然，这些都不是代码（“\”是一个等待发生的语法错误），但从这里实现应该不会太困难。在