在其一侧打印二叉树

Question

如何在其一侧打印二叉树以使输出看起来像这样？

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

范围蠕变：这将是e xcellent如果你可以传入一个函数来返回字符串来打印任何节点;通过这种方式，我有时也可以打印有关非离开节点的信息。因此，节点是否有任何要打印的内容是由作为参数传入的函数来控制的。

这里的一些测试数据在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

下面是一些代码，实现在别处描述的一般，递归方法。树的内部表示是一个字符串（叶）或一个元组（子对）的子节点。节点的中间“片段”的内部表示是元组(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 - 这就是说右边的“arm”有左边子树右边的长度（你需要阅读几次）。它使事情相对平衡。看到上面的不对称的例子。

更好地理解事情的一个好方法是修改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 

还有更多的解释here（虽然树是非常不同的）。

Answer 2

使一个表示的结构，涉及一个字符串数组和的“花瓣”一个行号。

代表（叶）为[0，再版（叶值）]

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

垫代表（顶部）中的每一行与如果上述顶部的花瓣空间，或者在下面的适当位置用斜线表示。同样，如果在底部的花瓣下方填充代表（底部）的每一行，或者在上面的适当位置加上反斜杠。 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"]] 

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

如果你愿意，你也可以在（花瓣1）行的每一个非叶（和所有其他行的额外空间）上添加一个“_”。

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

Answer 3

您需要递归处理，并跟踪各个子树的大小。特别是，根源在哪里。非平衡树可以很容易地是这样的：

/ 
\/ 
\/ 
    \/ 
    \ 

假如您现在已经建立了这个树，你有什么需要添加父级别时，此转换以下。

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

关键的想法是从树叶开始。它们是微不足道的。然后定义一种聚合两棵子树的方法，因为它们具有不同数量的线和子树根节点的不同位置。

Answer 4

这里是一个很好的侧身树刚帮我在调试一个项目： 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)