En primer recorrido inverso Amplitud en C #

Question

Cualquier persona tiene una implementación del algoritmo listo inversa Amplitud primer recorrido en C #?

Por Invertir primero en amplitud de recorrido, quiero decir, en lugar de buscar un árbol a partir de un nodo común, quiero buscar el árbol de la parte inferior y convergentes gradualmente a un nodo común.

El dejan ver el siguiente figura, esto es la salida de un primer recorrido Amplitud:

En mi primera inversa amplitud de recorrido, 9, 10, 11 y 12 serán los primeros nodos encontraron (el orden de ellos no son importantes ya que son todos de primer orden). 5, 6, 7 y 8 son los segundos pocos nodos encontraron, y así sucesivamente. 1 sería el último nodo encontró.

Cualquier idea o punteros?

Editar: Cambiar "búsqueda en anchura" a "Amplitud primer recorrido" para aclarar la cuestión

Answer 1

Ejecutar un BFS normales de rootNode y dejar depth[i] = linked list of nodes with depth i. Así que para su ejemplo, usted tendrá:

depth[1] = {1}, depth[2] = {2, 3, 4} etc.. Usted puede construir esto con una simple búsqueda BFS. A continuación, imprima todos los nodos en depth[maxDepth], a continuación, los de depth[maxDepth - 1] etc.

La profundidad de una i nodo es igual a la profundidad de su nodo padre + 1. La profundidad del nodo raíz puede considerarse 1 o 0.

Answer 2

El uso de una combinación de una pila y cola.

Haga lo BFS 'normales' que utilizan la cola (que supongo que usted sabe que hacer ya), y seguir empujando los nodos en la pila a medida que los encuentra.

Una vez hecho esto con el BFS, la pila contendrá el orden BFS inversa.