Wyświetlanie drzewa w ASCII

Question

Jako aktywność w czasie, postanowiłem zaimplementować strukturę (podobną) do Pythona w postaci Tree (podobnej).
I wdrożone Node klasy (który sam służy tutaj) tak:

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 

Jak widać funkcja display nie jest realizowany.
Oto przykład drzewa.

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') 

Oto przykładowe wyjście dla display.

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

W najkrótszej formie
Jak można „budować” drzewko ASCII (jak wyżej) z klasy Node ??

W dłuższej formie
„logika” druku jest:

1. Kiedy jest tylko jedno dziecko, | kładzie się nad dzieckiem. (D)
2. W przeciwnym razie, każde dziecko ma nad nim + (B, C, E, F)
3. Kiedy nie ma nawet. dzieci, ^ znajduje się poniżej rodzica. (A)
4. W przeciwnym razie (liczba dzieci jest nieparzysta) + jest umieszczany pod rodzicem. (C)

Myślałem o zaczynaniu od dołu. Zdałem sobie sprawę, że musi być wezwanie do każdego z dzieci, ale nie były w stanie wdrożyć niczego (tego rodzaju lub w inny sposób), które dał coś blisko.

Answer 1

Oto rozwiązanie, które obejmuje większość tego, czego szukasz.

Podobnie jak w przypadku dowolnego algorytmu drzewa, należy powtórzyć potomstwo drzewa i połączyć wyniki w każdym węźle. Oto sztuczka: display() zwraca prostokąt tekstu, na przykład:

aaaaaa 
aaaaaa 
aaaaaa 

Większość prostokąta będą spacje. Zwracanie tylko prostokątów tekstu ułatwia łączenie wyników. użyjemy dwóch następujących funkcji pomocniczych, jeden do pomiaru szerokości bloku, a drugi do łączenia w większe bloki poziomo bloków:

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

zobaczyć, gdzie to się dzieje? Dzieci zwracają prostokąt, który wyświetla siebie i ich potomków, a każdy węzeł połączy te prostokąty w większy prostokąt, który zawiera się. Reszta kodu renderuje kresek i plusów:

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) 

I jesteśmy na wyścigach!

       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       

(Wymagania jak „Umieszczenie^poniżej rodzica” są pozostawione jako ćwiczenie dla czytelnika)

Answer 2

Chciałbym zaproponować przyjrzeć modułu ETE http://ete.cgenomics.org który implementuje funkcjonalność opisz tutaj i wiele więcej.

Jednocześnie chciałbym podać ten wpis: Pretty Print output in a sideways tree format in console window, jeśli wcześniej zadano podobne pytanie. Jak widać w takiej dyskusji, funkcja _asciiArt z ETE zapewnia to, czego, jak sądzę, szukasz.

Mam nadzieję, że to pomaga,