Reverse Largura Primeira Travessal em C#

Question

Alguém tem uma implementação pronta do primeiro algoritmo reverso em largura de travessia em C#?

Ao largura reversa Primeira travessia, quero dizer, em vez de pesquisar uma árvore a partir de um nó comum, quero pesquisar a árvore de baixo e gradualmente convergir para um nó comum.

Vamos ver a figura abaixo, esta é a saída de uma primeira travessia:

Na minha largura reversa, a primeira travessia, 9,10,11 e 12 Serão os primeiros nós encontrados (a ordem deles não é importante, pois todos são de primeira ordem). 5, 6, 7 e 8 são os segundos poucos nós encontrados, e assim por diante. 1 seria o último nó encontrado.

Alguma ideia ou indicador?

Editar: Alterar "Pesquisa de largura" para "Livre First Traversal" para esclarecer a pergunta

Answer 1

Execute um BFS normal de rootNode e deixar depth[i] = linked list of nodes with depth i. Então, para o seu exemplo, você terá:

depth[1] = {1}, depth[2] = {2, 3, 4} etc.. Você pode construir isso com uma simples pesquisa de BFS. Em seguida, imprima todos os nós em depth[maxDepth], então aqueles em depth[maxDepth - 1] etc.

A profundidade de um nó i é igual à profundidade do nó do pai + 1. A profundidade do nó raiz pode ser considerada 1 ou 0.

Answer 2

Use uma combinação de pilha e fila.

Faça os BFs 'normais' usando a fila (que presumo que você já sabe fazer) e continue pressionando os nós na pilha enquanto os encontra.

Uma vez feito com o BFS, a pilha conterá a ordem BFS reversa.