Camminare su un albero, prima il genitore

Question

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

Answer 1

Codice pseudo:

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)
}

Modifica : ricorsivo o no?
Per essere tecnicamente corretto, e come sottolineato da AndreyT e altri in questo post, questo approccio è una forma di un algoritmo ricorsivo, in cui uno stack gestito esplicitamente viene usato al posto di dello stack della CPU e in cui la ricorsione ha luogo a livello del ciclo While. Detto questo, differisce da un'implementazione ricorsiva di per sé in un paio di modi sottili ma significativi:

• Solo le " variabili " vengono spinti nello stack; non esiste "stack frame" e l'indirizzo di restituzione associato nello stack, l'unico "indirizzo di restituzione" è implicito nel ciclo while e ne esiste solo un'istanza.
• Lo " stack " potrebbe essere usato come un elenco per cui il prossimo "frame" potrebbe essere portato ovunque nell'elenco, senza frenare in alcun modo la logica.

Answer 2

Breadth First Search

Answer 3

Stai cercando un attraversamento preordine. Penso che puoi farlo in modo non ricorsivo una coda:. In pseudocodice:

Crea una coda vuota, quindi invia il nodo principale.

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

Answer 4

Se hai collegamenti a tutti i bambini e anche al genitore, l'algoritmo non ricorsivo è piuttosto banale. Dimentica che hai un albero. Pensalo è un labirinto in cui ogni legame genitore-figlio è un normale corridoio bidirezionale da una giunzione all'altra. Tutto ciò che devi fare per percorrere l'intero labirinto è quello di svoltare nel corridoio successivo a sinistra ad ogni incrocio. (In alternativa, pensalo come camminare nel labirinto con la mano sinistra, toccando sempre il muro sul lato sinistro). Se inizi dal bivio (e ti sposti in qualsiasi direzione), camminerai sull'intero albero visitando sempre i genitori prima dei bambini. Ogni "corridoio" in questo caso verranno percorse due volte (in una direzione e nell'altra) e ciascuna "giunzione" (nodo) sarà visitato tante volte quante sono i "corridoi" unisciti a esso.

Answer 5

Utilizza un set di nodi. Metti il ??root nel set per iniziare. Quindi, in un ciclo, estrarre un nodo dal set, visitarlo, quindi mettere i suoi figli nel set. Quando il set è vuoto, il gioco è fatto.

Answer 6

In pseudocodice:

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

Answer 7

Se inizi dal nodo radice e visiti solo i genitori / figli dei nodi che hai già visitato, non c'è nessun modo di attraversare l'albero in modo tale da visitare un nodo prima di visitare i suoi antenati .

Qualsiasi tipo di attraversamento, profondità prima (ricorsiva / basata sullo stack), larghezza prima (basata sulla coda), profondità limitata o semplicemente estrazione di un set non ordinato, funzionerà.

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

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

Answer 8

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

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

Answer 9

Ecco un approccio veramente non ricorsivo: nessuno stack, spazio costante. Questo codice Python presuppone che ciascun nodo contenga un elenco di elementi secondari e che gli oggetti nodo non definiscano l'uguaglianza, pertanto la funzione "indice" confronta le 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 migliorato un po ', reso più conciso e più facile da leggere, ma questo è il senso.

Answer 10

Costruisci un elenco di nodi alla radice (livello 0), itera su ogni nodo a sua volta e cerca i figli diretti (il cui nodo genitore è il nodo da cui stiamo attualmente cercando) (livello 1), quando termina con il livello 0 passa al livello iterante 1 e così via fino a quando non hai più nodi non visitati.