Algoritmo per l'attraversamento di alberi

Question

Aggiornamento:
ho trovato più di un esempio di quello che sto cercando di tirare fuori: Managing Hierarchical Data in MySQL. Voglio farlo ma in JavaScript perché sto costruendo un'app che contiene commenti che si trovano in una struttura gerarchica, per essere più specifici su reddit.com. Se hai l'estensione Pretty JSON sul tuo browser Chrome, vai su reddit e fai clic sui commenti di un thread e poi aggiungi .json all'URL per vedere cosa sto analizzando.
Ottengo i dati JSON bene, è solo analizzando i commenti e aggiungendo l'HTML appropriato per mostrare che è annidato.
Idee per soluzioni?

---

domanda VECCHIO:
Sto lavorando su un programma e io sono venuto ad una parte che ho bisogno di capire la logica prima di scrivere il codice. Sto raccogliendo dati che sono in un formato ad albero ma con la possibilità di diversi bambini per ciascun nodo genitore e l'unico albero in cui riesco a trovare i dati sono alberi con pesi o alberi dove al massimo ogni nodo ha due nodi figli. Così sto cercando di capire l'algoritmo per valutare ogni nodo di un albero come questo:

startingParent[15] // [# of children] 
    child1[0] 
    child2[5] 
     child2ch1[4] 
     ... 
     child2ch5[7] 
    child3[32] 
    ... 
    child15[4] 

Ora, quando provo a scrivere in che modo il mio algoritmo funzionerebbe finisco scrittura nidificati per/while, ma io finiscono per scrivere un ciclo per ogni livello dell'altezza dell'albero che, per dati dinamici e alberi di altezza sconosciuta con un numero sconosciuto di bambini per nodo, non funziona. So che ad un certo punto ho imparato come attraversare un albero come questo, ma mi sta completamente sfuggendo proprio ora. Qualcuno sa come si fa in termini di loop?

Answer 1

Se non si utilizzerà la ricorsione, è necessaria una struttura dati ausiliaria. Una coda ti darà una traversata in ampiezza, mentre una pila ti darà una traversata in profondità. In entrambi i casi sembra più o meno in questo modo:

structure <- new stack (or queue) 
push root onto structure 
while structure is not empty 
    node <- pop top off of structure 
    visit(node) 
    for each child of node 
    push child onto structure 
loop 

Wikipedia Riferimenti

• Queue
• Stack

Answer 2

Utilizzare la ricorsione, non i loop.
Breadth first search
Depth first search
Questi dovrebbero aiutarti a iniziare con quello che si sta cercando di realizzare

Answer 3

Proprio usare la ricorsione come

def travel(node): 
    for child in node.childs: 
     # Do something 
     travel(child) 

Answer 4

Il codice più semplice per la maggior parte l'attraversamento di alberi di solito è ricorsivo. Per un albero a più vie come il tuo, di solito è più semplice avere un ciclo che guarda ogni puntatore a un bambino e chiama se stesso con quel nodo come argomento, per tutti i nodi figlio.