Reverse Larghezza primo attraversamento in C #

Question

Chiunque dispone di un'implementazione pronto dell'algoritmo Reverse Larghezza primo attraversamento in C #?

Di Inverti Larghezza primo attraversamento, voglio dire, invece di cercare un albero a partire da un nodo comune, voglio cercare l'albero dal basso e gradualmente convergente ad un nodo comune.

Vediamo i sotto figura, questo è l'uscita di un primo attraversamento Larghezza:

Nel mio rovescio ampiezza primo attraversamento, 9, 10, 11 e 12 saranno i primi nodi trovato (l'ordine di loro non sono importanti in quanto sono tutti di primo ordine). 5, 6, 7 e 8 sono la seconda nodi poche trovati, e così via. 1 sarebbe l'ultimo nodo trovato.

Tutte le idee o puntatori?

Modifica: Modifica "ricerca in ampiezza" a "Larghezza Prima traversal" per chiarire la questione

Answer 1

Esegui un normale BFS da rootNode e lasciare depth[i] = linked list of nodes with depth i. Così, per il tuo esempio avrete:

depth[1] = {1}, depth[2] = {2, 3, 4} etc.. È possibile costruire questo con una semplice ricerca BFS. Poi stampare tutti i nodi depth[maxDepth], poi quelli in depth[maxDepth - 1] etc.

La profondità di un i nodo è uguale alla profondità del suo nodo padre + 1. La profondità del nodo radice può essere considerato 1 o 0.

Answer 2

L'uso di una combinazione di una pila e una coda.

Fare la 'normali' BFS utilizzando la coda (che presumo si sa fare già), e mantenere i nodi che spingono in pila come li si incontra.

Una volta fatto con la BFS, lo stack conterrà l'ordine inverso BFS.