Reverse Breite Erste Traversal in C #

Question

Jeder hat eine fertige Implementierung des Reverse-Breite Ersten Traversierungsalgorithmus in C #?

Mit dem Reverse-Breite Ersten Traversal, meine ich stattdessen einen Baum von der Suche von einem gemeinsamen Knoten beginnen, ich mag den Baum aus dem Boden suchen und konvergenten allmählich zu einem gemeinsamen Knoten.

Lassen Sie uns die Abbildung unten sehen, ist dies die Ausgabe einer Breite Erste Traversal:

In meinem Rückwärtsbreiten Traversal, 9, 10, 11 und 12 wird die ersten Knoten gefunden (die Reihenfolge von ihnen ist nicht wichtig, da sie alle erste Ordnung sind). 5, 6, 7 und 8 sind die zweiten wenige Knoten gefunden, und so weiter. 1 wäre der letzte Knoten gefunden.

Irgendwelche Ideen oder Hinweise?

Edit: Ändern „Breitensuche“ auf „Breiten Erste Traversal“, um die Frage zu klären,

Answer 1

Führen Sie einen normalen BFS von rootNode und lassen depth[i] = linked list of nodes with depth i. So für Ihr Beispiel musst du:

depth[1] = {1}, depth[2] = {2, 3, 4} etc.. Sie können mit einem einfachen BFS-Such bauen diese. Dann werden alle Knoten in depth[maxDepth] drucken, dann diejenigen, die in depth[maxDepth - 1] etc.

Die Tiefe eines Knotens i ist gleich der Tiefe der Vater-Knoten + 1. Die Tiefe des Wurzelknotens 1 oder 0 betrachtet werden kann.

Answer 2

verwendet eine Kombination aus einem Stapel und Warteschlangen.

Haben die ‚normalen‘ BFS mit der Warteschlange (was ich nehme an, Sie wissen schon zu tun), und weiter pushen Knoten auf dem Stapel, wie Sie sie treffen.

Nachdem mit dem BFS getan, der Stapel wird umgekehrt BFS Reihenfolge enthalten.