以ASCII格式顯示樹

Question

作爲一個時間通過活動，我決定在python中實現一個Tree（like）結構。
我實現了一個Node類（一個人在這裏起到的目的），像這樣：

class Node: 
    def __init__(self, name, parent, *data): 
     self.name = name 
     self.parent = parent 
     self.data = data 
     self.children = [] 
     self.is_root = False 

    def __repr__(self): 
     return 'Node '+repr(self.name) 

    def dic(self): 
     retval = {self:[]} 
     for i in self.children: 
      retval[self].append(i.dic()) 
     return retval 

    def display(self): # Here 
     pass 

    def has_children(self): 
     return bool(self.children) 

    def get_parent(self): 
     return self.parent 

    def add_child(self, name, *data): 
     child = Node(name, self,*data) 
     self.children.append(child) 
     return child 

正如你可以看到display功能未實現。
下面是一個示例樹。

A = Node('A',Node) 
A.is_root = True 
B = A.add_child('B') 
D = B.add_child('D') 
C = A.add_child('C') 
E = C.add_child('E') 
F = C.add_child('F') 
G = C.add_child('G') 

以下是display的一些示例輸出。

>>> A.display() 
    A 
    +-^-+ 
    B C 
    | +-+-+ 
    D E F G 
>>> C.display() 
    C 
+-+-+ 
E F G 

在最短的形式，
我怎樣才能「打造」的ASCII樹（如上）從Node類？

在一個較長的形式，
的「邏輯」印刷是：

1. 當只有一個孩子，|子上面放置。 （D）
2. 否則，每個孩子都有一個+以上它，（B，C，E，F）
3. 當甚至沒有。的兒童，^放在家長的下方。 （A）
4. 否則，（有奇數的孩子）+放在父母的下方。 （C）

我一直在想從下面開始。 我意識到必須要給每個孩子打一個電話，但一直無法執行任何（這種或那種）任何接近它的任何東西。

Answer 1

下面是一個解決方案，涵蓋了你正在尋找的大部分。

像任何樹算法一樣，遞歸樹的子元素，並在每個節點上合併結果。這裏的竅門：display()返回文本的矩形區域，例如：

aaaaaa 
aaaaaa 
aaaaaa 

多數矩形的將是空白。只返回文本的矩形可以很容易地合併結果。我們將使用下面的兩個輔助功能，一個測量塊寬度，和對方塊水平結合成更大的塊：

def block_width(block): 
    try: 
     return block.index('\n') 
    except ValueError: 
     return len(block) 

def stack_str_blocks(blocks): 
    """Takes a list of multiline strings, and stacks them horizontally. 

    For example, given 'aaa\naaa' and 'bbbb\nbbbb', it returns 
    'aaa bbbb\naaa bbbb'. As in: 

    'aaa + 'bbbb = 'aaa bbbb 
    aaa'  bbbb'  aaa bbbb' 

    Each block must be rectangular (all lines are the same length), but blocks 
    can be different sizes. 
    """ 
    builder = [] 
    block_lens = [block_width(bl) for bl in blocks] 
    split_blocks = [bl.split('\n') for bl in blocks] 

    for line_list in itertools.izip_longest(*split_blocks, fillvalue=None): 
     for i, line in enumerate(line_list): 
      if line is None: 
       builder.append(' ' * block_lens[i]) 
      else: 
       builder.append(line) 
      if i != len(line_list) - 1: 
       builder.append(' ') # Padding 
     builder.append('\n') 

    return ''.join(builder[:-1]) 

看到這是怎麼回事？兒童返回一個顯示自己及其後代的矩形，每個節點將這些矩形組合成一個更大的包含自身的矩形。代碼的其餘部分只是呈現破折號和加號：

class Node: 
    def display(self): # Here 
     if not self.children: 
      return self.name 

     child_strs = [child.display() for child in self.children] 
     child_widths = [block_width(s) for s in child_strs] 

     # How wide is this block? 
     display_width = max(len(self.name), 
        sum(child_widths) + len(child_widths) - 1) 

     # Determines midpoints of child blocks 
     child_midpoints = [] 
     child_end = 0 
     for width in child_widths: 
      child_midpoints.append(child_end + (width // 2)) 
      child_end += width + 1 

     # Builds up the brace, using the child midpoints 
     brace_builder = [] 
     for i in xrange(display_width): 
      if i < child_midpoints[0] or i > child_midpoints[-1]: 
       brace_builder.append(' ') 
      elif i in child_midpoints: 
       brace_builder.append('+') 
      else: 
       brace_builder.append('-') 
     brace = ''.join(brace_builder) 

     name_str = '{:^{}}'.format(self.name, display_width) 
     below = stack_str_blocks(child_strs) 

     return name_str + '\n' + brace + '\n' + below 

    # SNIP (your other methods) 

而且我們正在參加比賽！

       a        
+-+-+---------------------------+       
b e f       g       
+  +-+-------------------------+       
c  h i       k       
+  + +-+-+-+-------------+-------------+-+------+  
d  j l m p r    s    O P  Q  
      + + +-+-+-+---------+    +-----+  
      n q t u w x   y    R  S  
      +  +  +-------+-------+  +---+---+ 
      o  v  z  A  M  T U Z 
          +-+-+-+-+-+-+ +   + + 
          B D E H I K L N   V a 
          + + +    +-+-+ + 
          C F J    W X Y b 
           +       
           G       

（需求，如「放置^低於母」被作爲練習留給讀者）

Answer 2

我想建議看看ETE模塊http://ete.cgenomics.org它實現你的功能在這裏描述等等。

與此同時，我想提供這個條目Pretty Print output in a sideways tree format in console window在哪裏有類似的問題已經問過。正如你在這樣的討論中看到的那樣，ETE的_asciiArt函數提供了我認爲你正在尋找的東西。

我希望這有助於