Camminare un albero, genitore prima

Question

Qual è il modo migliore per visitare tutti i nodi di un albero collegato (tutti i nodi hanno riferimenti a genitore e tutti i figli, i nodi radice hanno null come genitore), in modo che nessun nodo venga visitato prima di qualsiasi dei suoi antenati? Punti Brownie per non ricorsivi.

Answer 1

Pseudo codice:

NodesToVisit = some stack or some list 
NodesToVisit.Push(RootNode) 

While NodesToVisit.Length > 0 
{ 
    CurNode = NodesToVisit.Pop() 
    For each Child C in CurNode 
     NodesToVisit.Push(C) 
    Visit(CurNode) (i.e. do whatever needs to be done) 
} 

Edit: ricorsivo o no?
Per essere tecnicamente corretta, e come indicato dalla AndreyT e altri in questo post, questo approccio è una forma di un algoritmo ricorsivo, per cui uno stack esplicito gestiti, in sostituzione della pila CPU e dove la ricorsione si svolge a livello del ciclo While. Detto questo, si differenzia da un'implementazione ricorsiva per sé in un paio di sottili modi ma significativi:

• Solo "variabili" vengono inseriti nello stack; non c'è uno "stack frame" e l'indirizzo di ritorno associato nello stack, l'unico "indirizzo di ritorno" è implicito nel ciclo while, e c'è solo una sua istanza.
• Lo "stack" poteva essere usato come una lista in cui il successivo "frame" poteva essere portato ovunque nella lista, senza frenare la logica in alcun modo.

Answer 2

Creare un elenco di nodi nella radice (livello 0), scorrere su ciascun nodo a sua volta e cercare i figli diretti (il cui nodo padre è il nodo da cui stiamo attualmente cercando) (livello 1), una volta terminato con il livello 0 passa al livello 1 di iterazione e così via fino a quando non ci sono nodi non visitati rimanenti.

Answer 3

Utilizzare un set di nodi. Metti la radice nel set per iniziare. Quindi, in un ciclo, estrai un nodo dal set, visitalo, quindi metti i suoi figli nel set. Quando il set è vuoto, hai finito.

Answer 4

In pseudocodice:

currentList = list(root) 
nextList = list() 
while currentList.count > 0: 
    foreach node in currentList: 
     nextList.add(node.children) 
    currentList = nextList 

Answer 5

Siete alla ricerca di un attraversamento preordine. Penso che puoi farlo senza ricorsività con la una coda :. In pseudocode:

Creare una coda vuota, quindi premere il nodo radice.

while nonempty(q) 
    node = pop(q) 
    visit(node) 
    foreach child(node) 
    push(q,child) 

Answer 6

Breadth First Search

Answer 7

Se si avvia al nodo radice, e visitare solo i genitori/figli dei nodi che hai già visitato, non c'è alcun modo per attraversare l'albero in modo tale che si visita un nodo prima di visitare i suoi antenati.

Qualsiasi tipo di attraversamento, profondità prima (ricorsiva/basata su stack), larghezza prima (in base alla coda), profondità limitata o semplicemente estrazione da un set non ordinato, funzionerà.

Il metodo "migliore" dipende dall'albero. Larghezza prima funzionerebbe bene per un albero molto alto con pochi rami. La profondità prima funzionerebbe bene per gli alberi con molti rami.

Poiché i nodi hanno effettivamente dei puntatori ai loro genitori, esiste anche un algoritmo a memoria costante, ma è molto più lento.

Answer 8

Se si hanno anche collegamenti a tutti i bambini e al genitore, l'algoritmo non ricorsivo è piuttosto banale. Dimentica che hai un albero. Pensa che è un labirinto in cui ogni collegamento genitore-figlio è un normale corridoio bidirezionale da una giunzione all'altra. Tutto quello che devi fare per percorrere l'intero labirinto è girare nel prossimo corridoio a sinistra ad ogni incrocio. (In alternativa, pensaci come se camminassi nel labirinto con la mano sinistra che tocca sempre il muro sul lato sinistro). Se parti dal nodo radice (e ti muovi in ​​qualsiasi direzione), percorrerai l'intero albero visitando sempre i genitori prima dei bambini. Ogni "corridoio" in questo caso sarà percorso due volte (in una direzione e nell'altra), e ogni "giunzione" (nodo) sarà visitata tante volte quante "corridoi" si uniranno a essa.

Answer 9

Non sarei d'accordo con l'ampiezza della prima ricerca poiché la complessità dello spazio è spesso la rovina di quell'algoritmo di ricerca specifico. Probabilmente l'uso dell'algoritmo di approfondimento iterativo è un'alternativa migliore per questo tipo di utilizzo e copre lo stesso tipo di attraversamento della ricerca per ampiezza. Ci sono alcune piccole differenze nell'affrontare il margine della ricerca in ampiezza, ma non dovrebbe essere troppo difficile da codificare (pseudo).

Riferimento: http://en.wikipedia.org/wiki/Iterative_deepening

Answer 10

Ecco un veramente approccio non ricorsivo: nessuna pila, spazio costante. Questo codice Python presuppone che ogni nodo contiene un elenco dei bambini, e che gli oggetti nodo non definiscono l'uguaglianza, in modo che la funzione di 'indice' è il confronto delle identità:

def walkTree(root, visit_func): 
    cur = root 
    nextChildIndex = 0 

    while True: 
     visit_func(cur) 

     while nextChildIndex >= len(cur.children) and cur is not root: 
      nextChildIndex = cur.parent.children.index(cur) + 1 
      cur = cur.parent 

     if nextChildIndex >= len(cur.children): 
      break 

     cur = cur.children[nextChildIndex] 
     nextChildIndex = 0 

sono sicuro che potrebbe essere ripulito un po ', reso più conciso e più facile da leggere, ma questo è il succo.