Was bedeutet ein Spaziergang vor, nach und in der Reihenfolge für einen Baum?
8
Die in diesem Wikipedia-Artikel erläuterten Baumdurchquerungsmethoden sind Vorbestellung, Nachbestellung und In-Reihenfolge. Sind diese Methoden auf Binärbäume beschränkt? Der Algorithmus scheint als linkes und rechtes Kind definiert zu sein. Wenn es für n-ary Bäume verwendet werden kann, wie?
Ein n-ary Baum hat 1 Elternteil und n Kinder an einem bestimmten Knoten. Wobei n eine beliebige ganze Zahl für jeden Knoten sein kann.
Bitte verwenden Sie die folgende Abbildung, um dies zu erklären, falls Sie eine benötigen.
Nein, es ist nicht auf Binärbäume beschränkt. Ja, Vorbestellung und Nachbestellung können für verwendet werdenn-ary Bäume. Sie ersetzen einfach die Schritte "Durchqueren des linken Teilbaums .... Durchqueren des rechten Teilbaums ...." im Wikipedia-Artikel durch "Für jedes Kind: Durchlaufen des Teilbaums, der bei diesem Kind verwurzelt ist, durch rekursives Aufrufen der Durchquerungsfunktion". Wir gehen davon aus, dass die for-Schleife die untergeordneten Elemente in der Reihenfolge durchläuft, in der sie in der Datenstruktur enthalten sind: normalerweise in der Reihenfolge von links nach rechts für ein Diagramm, wie Sie es gezeigt haben.
Tatsächlich ist dies bereits im Wikipedia-Artikel über Baumdurchquerungen beschrieben: siehe https://en.wikipedia.org/wiki/Tree_traversal#Generic_tree , in dem genau beschrieben wird, wie dies verallgemeinert werden solln-ary Bäume. Bei der Vorbestellungsüberquerung lautet die Vorbestellungsoperation "Aktuellen Knoten anzeigen" und die Nachbestellungsoperation "Nichts tun". Nachbestellungsdurchlauf ist einer, bei dem die Vorbestellungsoperation "Nichts tun" und die Nachbestellungsoperation "Aktuellen Knoten anzeigen" lautet.
In-Order-Traversal ist ein Sonderfall. Es ist wahrscheinlich nur für binäre Bäume sinnvoll. Es gibt zwar verschiedene Möglichkeiten, für die man die Durchquerung in der Reihenfolge definieren kannn-ary Bäume, jeder von ihnen fühlt sich ein bisschen seltsam und unnatürlich und wahrscheinlich nicht besonders nützlich in der Praxis. Daher ist es wahrscheinlich am besten, sich das Durchlaufen in der Reihenfolge als spezifisch für Binärbäume vorzustellen. wenn Sie etwas Ähnliches in der Reihenfolge Durchquerung für a tun möchtenn-ary Baum, müssen Sie genau entscheiden, was Sie damit meinen, da es dafür keine Standardbedeutung gibt.
Erwähnenswert ist auch, dass die eine Art von Durchquerung nicht funktioniert n-ary Bäume ist in Ordnung; Für einen Knoten mit einer ungeraden Anzahl von Kindern gibt es kein aussagekräftiges Äquivalent zur Inorder Traversal.
Adam R. Nelson
@ DW Was ist mit in-oder? Könnten Sie das bitte auch in Ihre Antwort aufnehmen?
Renae Lider
@ AdamR.Nelson Wie funktioniert es für eine andere gerade Zahl als zwei? Für Binär ist es Links-Wurzel-Rechts. Ich weiß nicht, wie es zum Beispiel für einen Quadtree funktionieren wird.
Renae Lider
@RenaeLider Bei Kindern mit den Namen A, B, C und D (von links nach rechts) können Sie etwas tun, das der Durchquerung eines Quadtree ähnelt, indem Sie AB-Root-CD durchlaufen. Aber ich denke nicht, dass es eine nützliche Anwendung dafür gibt.
Adam R. Nelson
2
@ AdamR.Nelson Sie können in der Reihenfolge für den allgemeinen Fall definieren, indem Sie sagen, dass Sie den Elternteil nach dem ersten Kind und dann die anderen Kinder besuchen. Vielleicht nicht sehr aussagekräftig, aber möglich.
Raphael
0
Es gibt viele exotische Datenstrukturen, die in ganz CS mit vielen Varianten verwendet werden. In letzter Zeit gab es eine ähnliche Frage (die jetzt gelöscht wurde), wie man n-ary Bäume in geordneter Weise durchquert overexchange. Es scheint, dass die meisten oder viele n-ary Bäume in der untersuchten Literatur dazu neigen, nicht geordnet zu werden. Als alternativer pov / außergewöhnlich / "Rand" -Fall für die andere detaillierte Antwort gibt es jedoch Fälle von geordneten n-ary Bäumen, die nicht "seltsam und unnatürlich und in der Praxis wahrscheinlich nicht besonders nützlich" sind. Hier ist eine Referenz; Es gibt wahrscheinlich viele andere Fälle, obwohl es möglich ist, dass sie nicht weit verbreitet sind.
ps Eine andere Möglichkeit, sich geordnete n-ary Bäume vorzustellen, besteht einfach darin, dass Kanten beschriftet sind und Ordnungen haben, auf die der Algorithmus beim Durchlaufen zugreifen kann.
vzn
Ich bin mir nicht sicher über das Einfüge- / Aktualisierungsverfahren des geordneten Stammbaums. Kannst du den Code teilen?
Es gibt viele exotische Datenstrukturen, die in ganz CS mit vielen Varianten verwendet werden. In letzter Zeit gab es eine ähnliche Frage (die jetzt gelöscht wurde), wie man n-ary Bäume in geordneter Weise durchquert
overexchange. Es scheint, dass die meisten oder viele n-ary Bäume in der untersuchten Literatur dazu neigen, nicht geordnet zu werden. Als alternativer pov / außergewöhnlich / "Rand" -Fall für die andere detaillierte Antwort gibt es jedoch Fälle von geordneten n-ary Bäumen, die nicht "seltsam und unnatürlich und in der Praxis wahrscheinlich nicht besonders nützlich" sind. Hier ist eine Referenz; Es gibt wahrscheinlich viele andere Fälle, obwohl es möglich ist, dass sie nicht weit verbreitet sind.[1] n-ary bestellte Bäume / P Mateti 7140 Kursnotizen
quelle