Inverser en largeur d'abord traversal en C #

Question

Toute personne a une mise en œuvre immédiate de l'ampleur inverse premier algorithme de traversal en C #?

Par inverse en largeur d'abord traversal, je veux dire au lieu de rechercher un départ d'arbre à partir d'un noeud commun, je veux chercher l'arbre du bas et convergé progressivement à un noeud commun.

Voyons voir la figure ci-dessous, c'est la sortie d'une largeur d'abord traversal:

Dans ma largeur inverse premier traversal, 9, 10, 11 et 12 seront les premiers noeuds trouvés (l'ordre d'entre eux ne sont pas importants car ils sont tous premier ordre). 5, 6, 7 et 8 sont les deuxièmes quelques noeuds trouvés, et ainsi de suite. 1 serait le dernier noeud trouvé.

Toutes les idées ou des pointeurs?

Modifier: Modification de clarifier la question « Première recherche Largeur » à « Largeur Première traversal »

Answer 1

Exécuter un BFS normal à partir rootNode et laisser depth[i] = linked list of nodes with depth i. Donc, pour votre exemple, vous aurez:

depth[1] = {1}, depth[2] = {2, 3, 4} etc.. Vous pouvez construire ce avec une simple recherche BFS. Ensuite, imprimez tous les nœuds depth[maxDepth], puis ceux depth[maxDepth - 1] etc.

La profondeur d'un noeud i est égale à la profondeur de son noeud père + 1. La profondeur du nœud racine peut être considéré comme 1 ou 0.

Answer 2

A l'aide d'une combinaison d'une pile et la file d'attente.

Faites la « normale » BFS en utilisant la file d'attente (que je suppose que vous savez faire déjà), et continuer à pousser les nœuds sur la pile que vous les rencontrez.

Une fois fait avec le BFS, la pile contiendra l'ordre inverse BFS.