einen binären Baum auf seiner Seite drucken

Question

Wie können Sie einen binären Baum auf seiner Seite drucken, so dass die Ausgabe so aussieht?

__/a 
__/ \b 
    \ _/c 
    \_/ \d 
    \e 

_{(Prettier ascii-art willkommen)}

Hier ist ein Code, der nicht ganz funktioniert:

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,"")  

Welche diese Ausgänge:

 _/hg19 
    _/ \rheMac2 
    _/ \mm9 
    /\_/bosTau4 
/\_/canFam2 
_/  \pteVam1 
\_/loxAfr3 
    \dasNov2 

Scope kriechen: es wäre e xcellent, wenn Sie eine Funktion übergeben können, die die zu druckende Zeichenfolge eines beliebigen Knotens zurückgibt; Auf diese Weise kann ich manchmal auch Informationen über Nicht-Leave-Knoten drucken. Ob ein Knoten also etwas zu drucken hat, wird von der Funktion gesteuert, die als Parameter übergeben wird.

Hier einige Test-Daten in 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

Hier einige Code, der den allgemeinen, rekursive Ansatz an anderer Stelle beschrieben implementiert. Die interne Repräsentation eines Baumes ist entweder eine Zeichenkette (Blatt) oder ein Tupel (Paar) von Unterknoten. Die interne Darstellung des intermediären "Fragments" eines Knotens ist das Tupel (above, below, lines), wobei above und below die Anzahl der Zeilen über und unter der Wurzel sind und lines ein Iterator über jede Teilzeile ist (ohne Leerzeichen auf der linken Seite).

#!/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)) 

Hier ist ein Beispiel einer Ausgabe:

  _/rrrr 
     _/ \_/rrrlr 
    /\ \rrrll 
    _/ \_/rrlr 
    /\  \rrll 
/ \ _/rlrr 
/ \_/ \rlrl 
_/  \_/rllr 
\   \_/rlllr 
    \   \rllll 
    \  _/lrrr 
    \  _/ \lrrl 
    \ /\_/lrlr 
     \_/ \lrll 
     \ _/llrr 
     \_/ \llrl 
      \_/lllr 
      \_/llllr 
       \lllll 

Und ein bisschen mehr asymmetrische eine, vielleicht zeigt, warum ich mit Leerzeichen nach links bis zum Ende (über flatten) nicht Pad Linien tun. Wäre die untere Hälfte links gepolstert worden, würde ein Teil des Oberarms den Polsterbereich durchqueren.

Es ist der "offensichtliche" rekursive Algorithmus - der Teufel steckt im Detail. Es war am einfachsten ohne das "_" zu schreiben, was die Logik etwas komplexer macht.

Vielleicht ist die einzige "Einsicht" gap_above = l_above - das heißt, dass der rechte "Arm" die Länge der rechten Seite des linken Teilbaums hat (Sie müssen das ein paar Mal lesen). Es macht die Dinge relativ ausgeglichen. Siehe das obige asymmetrische Beispiel.

Eine gute Möglichkeit, Dinge genauer zu verstehen, ist die Routine zu ändern, um ein Zeichen anstelle von ' ' zu nehmen und ein anderes Zeichen für jeden Anruf zu geben. Dann können Sie genau sehen, welche Logik welchen Raum erzeugt hat. Dies ist, was Sie für die Anrufe zu Pad von oben nach unten mit A, B, C und D erhalten, über (natürlich kein Zeichen gibt es, wenn die Menge an Speicherplatz Null ist):

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

Es gibt mehr Erklärung here (obwohl der Baum sehr leicht anders ist).

Answer 2

eine Darstellung Struktur Stellen, eine String-Array beteiligt und eine Zeilennummer des "Blütenblattes".

rep (Blatt) [0, repr (Blattwert)]

rep (Nichtblatt) gegeben top = nonleaf.left und bottom = nonleaf.right:

Pad jede Zeile rep (oben) mit Leerzeichen, wenn oben Blütenblatt Spitzen oder mit einem Schrägstrich an einer geeigneten Stelle, wenn darunter. Packen Sie außerdem jede Zeile von rep (unten) mit Leerzeichen unter dem Blütenblatt des unteren Rands oder mit einem umgekehrten Schrägstrich an einer geeigneten Position, falls darüber. repr (nonleaf) ist dann [Höhe des oberen, gepolsterte Zeilen des oberen, gefolgt von gepolsterten Zeilen des unteren].

Beispiel:

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

anzumerken, dass in oberem Fall ist die Breite des Polsters die Anzahl von Zeilen unter Blütenblatt ist; im unteren Fall entspricht die Breite der Polsterung dem Blütenblatt. Im Fall von (abcde) hat top also 2 Zeilen und petal 1, also ist padding (2 - 1 == 1) ein Zeichen; Boden hat Blütenblatt 2, also ist das Auffüllen 2 Zeichen.

Wenn Sie möchten, können Sie auch ein "_" an jeder freien Seite bei (Petal-1) ten Zeile (und ein zusätzliches Leerzeichen an alle anderen Zeilen) hinzufügen.

Offensichtlich ist nichts davon Code ("\" ist ein Syntaxfehler, der darauf wartet, zu passieren), aber es sollte nicht zu schwierig sein, von hier zu implementieren.

Answer 3

Sie müssen sich diesem rekursiv nähern und die Größen der einzelnen Teilbäume verfolgen. Insbesondere, wo die Wurzel ist. Eine nicht ausgeglichene Baum kann so leicht aussehen:

/ 
\/ 
\/ 
    \/ 
    \ 

Betrachten wir nun haben Sie bereits diesen Baum gebaut, was Sie tun dies auf die folgende müssen verwandeln, wenn die übergeordnete Ebene hinzufügen.

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

Die Schlüsselidee ist, mit den Blättern zu beginnen. Sie sind trivial. Definieren Sie dann eine Möglichkeit, zwei Teilbäume zu aggregieren, vorausgesetzt, sie haben eine andere Anzahl von Zeilen und eine andere Position des Teilbaum-Stammknotens.

Answer 4

Hier ist ein schöner Baum, der zur Seite half mir gerade ein Projekt in Debugging: http://www.acooke.org/cute/ASCIIDispl0.html

Ergebnisse der Verzeichnisstruktur des VIM NERDtree Plugin ähneln, wenn Sie das gesehen haben.

Hier ist meine Neuimplementierung als __str__ Verfahren in einem binären Baum:

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)