Anzeigen eines Baums in ASCII

Question

Als eine Zeitüberschreitung Aktivität, beschloss ich, eine Tree (like) Struktur in Python zu implementieren.
ich implementiert eine Node Klasse (die allein dem Zweck dient hier) wie folgt:

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 

Wie Sie die display Funktion sehen nicht implementiert.
Hier ist ein Beispielbaum.

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

Hier ist eine Beispielausgabe für display.

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

In kürzester Form,
Wie kann ich "bauen" ein ASCII-Baum (wie oben) von der Node-Klasse ??

In einer längeren Form,
Die "Logik" des Druckens:

1. Wenn dort nur ein Kind ist, | über dem Kind gestellt. (D)
2. Sonst, Jedes Kind hat eine + darüber, (B, C, E, F)
3. Wenn es auch keine gibt. von Kindern, ^ wird unter dem Elternteil gesetzt. (A)
4. Sonst, (es gibt ungerade Nr. Von Kindern) + wird unter dem Elternteil gesetzt. (C)

Ich habe überlegt, von unten zu beginnen. Ich erkannte, dass es einen Aufruf an jedes der Kinder geben muss, aber war nicht in der Lage, irgendetwas (von dieser Art oder auf andere Weise) zu implementieren, die irgendetwas nahelegte.

Answer 1

Hier ist eine Lösung, die das meiste abdeckt, wonach Sie suchen.

Wie alle Baumalgorithmen rekursieren Sie die untergeordneten Elemente des Baums und kombinieren Sie die Ergebnisse an jedem Knoten. Hier ist der Trick: display() ein Rechteck von Text gibt, zum Beispiel:

aaaaaa 
aaaaaa 
aaaaaa 

Der größte Teil des Rechtecks ​​Leerzeichen wird. Wenn nur Textrechtecke zurückgegeben werden, können Ergebnisse einfach kombiniert werden. Wir werden die folgenden zwei Hilfsfunktionen verwenden, nur einen Block Breiten zu messen, und die anderen Blöcke zu kombinieren, horizontal in größere Blöcke:

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

sehen, wohin dieses geht? Kinder geben ein Rechteck zurück, das sich selbst und ihre Nachkommen anzeigt, und jeder Knoten kombiniert diese Rechtecke zu einem größeren Rechteck, das sich selbst enthält. Der Rest des Codes macht nur die Bindestriche und Pluspunkte:

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) 

Und wir sind zu den Rennen!

       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       

(Anforderungen wie für den Leser sind links als Übung „a^unter der übergeordneten Platzierung“)

Answer 2

Ich mag würde vorschlagen einen Blick auf ETE Modul http://ete.cgenomics.org denen zu nehmen implementiert die Funktionalität, die Sie Beschreibe hier und vieles mehr.

Gleichzeitig möchte ich diesen Eintrag Pretty Print output in a sideways tree format in console window zur Verfügung stellen, wo eine ähnliche Frage zuvor gestellt wurde. Wie Sie in dieser Diskussion sehen können, bietet die Funktion _asciiArt von ETE, was Sie suchen.

Ich hoffe, das hilft,