stampa un albero binario su un lato

Question

Come è possibile stampare un albero binario su un lato in modo che l'output sia simile?

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

_{(Prettier ascii-art di benvenuto)}

Ecco un po 'di codice che non funziona del tutto:

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

Quali Risulterà:

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

Scope creep: sarebbe e xcellentissimo se potessi passare in una funzione che restituirà la stringa da stampare di qualsiasi nodo; in questo modo, a volte riesco a stampare informazioni sui nodi non lasciati. Quindi se un nodo ha qualcosa da stampare è controllato dalla funzione passata come parametro.

Ecco alcuni test-dati 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

Ecco alcuni codice che implementa il generale approccio, ricorsivo descritto altrove. La rappresentazione interna di un albero è una stringa (foglia) o una tupla (coppia) di sottonodi. La rappresentazione interna del "frammento" intermedio di un nodo è la tupla (above, below, lines), dove above e below sono il numero di linee sopra e sotto la radice e lines è un iteratore su ciascuna linea parziale (senza spazi a sinistra).

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

Ecco alcuni esempio di output:

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

E un po 'un altro asimmetrica che mostra, forse, perché non riempie le linee con spazi a sinistra fino alla fine (via flatten). Se la metà inferiore era stata imbottita a sinistra, parte del braccio avrebbe attraversato l'area imbottita.

   _/rrrrr 
      _/ \rrrrl 
      _/ \rrrl 
     _/ \_/rrlr 
     /\ \rrll 
    / \_/rlr 
    / \rll 
    /  /lrrr 
    /  _/ _/lrrlrr 
/ /\_/ \lrrlrl 
/ / \lrrll 
_/  _/  _/lrlrrr 
\ /\ _/ \lrlrrl 
    \ / \_/ \lrlrl 
    \_/  \lrll 
    \  _/llrrr 
     \ _/ \llrrl 
     \_/ \llrl 
     \lll 

È l'algoritmo ricorsivo "ovvio": il diavolo è nei dettagli. È stato più facile scrivere senza "_", il che rende la logica leggermente più complessa.

Forse l'unica "intuizione" è gap_above = l_above - che sta dicendo che il "braccio" giusto ha la lunghezza del lato destro della sottostruttura di sinistra (sarà necessario leggerlo alcune volte). Rende le cose relativamente equilibrate. Vedi l'esempio asimmetrico sopra.

Un buon modo per comprendere le cose in modo più dettagliato è modificare la routine pad per prendere un carattere anziché ' ' e assegnare un carattere diverso per ogni chiamata. Quindi puoi vedere esattamente quale logica ha generato quale spazio. Questo è quello che si ottiene utilizzando A. B, C e D per le chiamate al pad dall'alto verso il basso, al di sopra (ovviamente non c'è alcun carattere quando la quantità di spazio è zero):

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

C'è di più spiegazioni here (anche se l'albero è leggermente diverso).

Answer 2

Fai una struttura di rappresentanza, coinvolgendo un array di stringhe e un numero di riga del "petalo".

rep (foglio) è [0, repr (valore foglia)]

rep (non foglia), proposta top = nonleaf.left e bottom = nonleaf.right:

Pad ciascuna linea di rep (in alto) con spazi se sopra petalo top o con una barra in una posizione appropriata se di seguito. Allo stesso modo, tampona ciascuna linea di ripetizione (in basso) con spazi se sotto il petalo in basso, o con la barra rovesciata in una posizione appropriata se sopra. repr (nonleaf) è quindi [altezza delle righe superiori e superiori seguite dalle linee imbottite del fondo].

Esempio:

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

noti che nel caso sopra, la larghezza del riempimento è il numero di righe sotto petalo; nel caso in basso, la larghezza del padding corrisponde al petalo. Quindi, in (abcde) caso, top ha 2 righe e petalo 1, quindi padding è (2 - 1 == 1) un carattere; il fondo ha il petalo 2, quindi il riempimento è di 2 caratteri.

Se lo si desidera, è anche possibile aggiungere un "_" a ogni non foglia a (petal-1) th line (e uno spazio aggiuntivo a tutte le altre righe).

Ovviamente, niente di tutto ciò è codice ("\" è un errore di sintassi in attesa di verificarsi), ma non dovrebbe essere troppo difficile da implementare da qui.

Answer 3

È necessario avvicinarsi a questo in modo ricorsivo e tenere traccia delle dimensioni dei singoli sottoalberi. In particolare, dove si trova la radice. Un albero non equilibrata può facilmente apparire come segue:

/ 
\/ 
\/ 
    \/ 
    \ 

Ora consideriamo che avete già costruito questo albero, che cosa hai bisogno per trasformare questo al seguente quando si aggiunge il livello padre.

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

L'idea chiave è iniziare con le foglie. Sono banali. Quindi definire un modo per aggregare due sottoalberi, dato che hanno una diversa quantità di linee e una diversa posizione del nodo radice dell'albero secondario.

Answer 4

Ecco un bel albero di traverso che appena mi ha aiutato nel debug di un progetto: http://www.acooke.org/cute/ASCIIDispl0.html

risultati assomigliano la struttura di directory del plugin VIM NERDtree se hai visto che.

Qui è la mia ri-implementazione come metodo __str__ in un albero binario:

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)