Algoritmo per ottenere tutti i percorsi in un albero

Question

Algoritmo per ottenere tutti i percorsi in un albero

#1 da (4 voti)

1

Ho un albero che ha n livelli. Per esempio qui ho quattro livelli:

Ogni nodo ha due figli (tranne l'ultimo), tuttavia tutti tranne il primo e l'ultimo nodo di ogni riga hanno due genitori. Sto cercando di capire un modo scalabile per ottenere tutti i percorsi in un elenco di elenchi, in modo che per questo esempio avrò un elenco di elenchi di caratteri:

A,B,D,G

A,B,D,H

A,B,E,H

ecc.

Qualcuno può aiutarmi a orientarmi nella giusta direzione per trovare un algoritmo per questo indipendentemente da quanti livelli?

c# algorithms trees

posta Tyress 13.01.2016 - 11:36

fonte

1 risposta

Leggi altre domande sui tag c# algorithms trees

aggregazione DDD e struttura dei componenti [chiusa] La migliore pratica per scrivere esempi

score 4 · Accepted Answer

Il fatto che un nodo possa avere due genitori non dovrebbe impedirti di utilizzare una approfondita prima ricerca standard . Come lo descrivi, un bambino con due genitori è ancora parte indipendente di due "soluzioni". Il fatto che ci siano al massimo due bordi che escono da ciascun nodo semplifica ulteriormente le cose.

search(node):

    if node is null: // maybe a non-terminal parent's left or right was null
        return  // that or someone gave you a null graph

    add node to "discovered" list

    if node is terminal:
        print the list //[A,B,D,G], [A,B,D,H], etc
        remove node from the list
        return // done at this level

    search(node.left)
    search(node.right)
    remove node from the list // all done at this level

Puoi modificare l'ordine di scoperta andando a destra prima di andare a sinistra.