Es scheint mir wie Pre-Order-Traversal und DFS sind die gleichen wie in beiden Fällen, die wir bis zum Blattknoten in einer tiefen Weise durchlaufen. Könnte mich bitte jemand korrigieren, wenn ich falsch liege?Ist die Pre-Order-Traversierung auf einem Binärbaum gleich wie bei der Tiefensuche?
Vielen Dank im Voraus!
Vorbestellung ist eine Art von DFS.
Es gibt drei Arten von Tiefen-Traversierungen: Vorbestellung, In-Reihenfolge und Nach-Reihenfolge.
Auschecken here für weitere Informationen.
Es scheint mir, dass die Frage nicht eine erweiterte asnwer sucht, ich denke, er sucht nach DFS vorbestellen, die unter den üblichen Computer ist Hauptstudenten genannt "DFS" als kurzfristige. –
Ich glaube, er hat einfach beobachtet, dass, wenn der fragliche Graph auch ein Baum ist und der anfängliche Vertex für DFS die Wurzel des Baumes ist, DFS und eine Vorreihenfolge gleich sind. Die Traversierung in der richtigen Reihenfolge hat keine Bedeutung für k-ary-Bäume mit k> 2. – Dave
Auch wenn der Graph ein binärer Baum war, ist die Ausgabe des Traversals vor der Reihenfolge wahrscheinlich nicht mit einem Durchlauf des Vorgänger-Subgraphen identisch , es sei denn, die Scheitelpunkt-Adjazenzlisten werden konsistent in der gleichen Reihenfolge aufgelistet, wie sie als Knoten "Kinder" im Baum wären. Das heißt, die Graphendarstellung hat keine Vorstellung von "linken" und "rechten" Kindern. – Dave
Es hängt wahrscheinlich von der Definition und Implementierung des Tiefen- Algorithmus. Die DefaultMutableTreeNode Klasse der JTree Komponente Java Swing hat folgende Zählverfahren für Baumdurchlauf verwendet:
In Java Swing-Implementierung depthFirstEnumeration ist die gleiche wie die postOrderEnumeration. Meine Tests und die official documentation bestätigt dies.
Andere können definieren, was Tiefe zuerst bedeutet anders. Zum Beispiel gibt ein Artikel auf Wikipedia an, dass Vor-und Nachreihen-Durchquerungen spezifische Typen eines Tiefen-zuerst-Durchlaufs sind. Dies würde bedeuten, dass der Tiefen-First-Traversal kein konkreter Traversalalgorithmus ist.
Es wird nicht sein. Pre-Order hat eine strenge Art, den linken Knoten und dann den rechten Knoten zu besuchen. Aber für DFS kann es entweder so sein, wie es keine strenge Mode gibt. Es existiert also mehr als eine Traversierung basierend auf dem, was Sie auf den Stapel schieben.
http://en.wikipedia.org/wiki/Tree_traversal#Depth-first –