在其一側打印二叉樹

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)