Algoritmo di visualizzazione ad albero

Question

Esiste qualche algoritmo per la visualizzazione della struttura dati ad albero? Ho provato su Google, ma non ho trovato nessuno. Sono abbastanza sicuro che ci debba essere un algoritmo per questo compito non così semplice. O qualcuno ha qualche idea?

Answer 1

Presupposto: si desidera che ciascun nodo sia visualizzato in modo tale che sia centrato sopra i nodi figlio.

Per ottenere ciò, calcolare la larghezza di ciascun nodo, che definisco come la quantità di spazio orizzontale richiesta per visualizzare l'intera sottostruttura di questo nodo, in modo che non si sovrapponga con i suoi sottoalberi dei fratelli di sinistra o di destra.

Questo porta a:

width = 1 + sum(widths of children's nodes) 

Quindi, fare un attraversamento in profondità attraverso l'albero per calcolare la larghezza di ogni nodo. Per visualizzare, esegui una traversata in ampiezza per disegnare l'albero livello per livello.

Questa è la vaga idea di come procedere. Potresti voler modificare il calcolo della larghezza in base ai dettagli di come desideri rendere l'albero.

Answer 2

È possibile utilizzare il linguaggio DOT con graphviz ad esempio.

Answer 3

Tree-mapping è probabilmente quello che stai cercando. Graphviz è utile per visualizzare strutture grafiche non specializzate per strutture ad albero. Non sono riuscito a ritrovarlo ma ricordo di aver letto in un articolo scientifico che le treemaps (penso che i voronoi) siano ottimali per rappresentare strutture ad albero, per quanto riguarda il luogo che consumano e l'area può essere usata per rappresentare alcune unità (come la dimensione dei byte per esempio).

Here sono alcune alternative.

Here è una buona lista di articoli e altre informazioni sull'argomento.

Answer 4

È inoltre possibile stampare l'albero da sinistra a destra, ovvero radice all'estrema sinistra, il primo livello a destra e così via. Troverete l'albero stampato con ogni livello sulla propria 'colonna'. L'algoritmo è un po 'come questo:

print(node, spaces): 
    if node has left child: 
     print(left_child, spaces + ' ') 
    print spaces + node + '\n' 
    if node has right child: 
     print(right_child, spaces + ' ') 

Questo algoritmo stamperà un nodo albero per riga. Ogni livello dell'albero sarà rientrato a destra da alcuni spazi. Questo algoritmo stamperà gli articoli in ordine crescente, ma l'ordine decrescente può essere ottenuto elaborando prima il bambino giusto.