Entspricht die Vorbestellungsdurchquerung der Tiefensuche?

12

Mir scheint, dass Vorbestellungsdurchquerung und DFS gleich sind wie in beiden Fällen, in denen wir rekursiv von der Wurzel bis zum linken Zweig und zurück zur Wurzel und dann zum rechten Zweig durchlaufen. Könnte mich bitte jemand korrigieren, wenn ich falsch liege?

Danke im Voraus!

algorithms trees binary-tree graph-traversal Srikanth Kandalam
quelle

Antworten:

10

Pre-Order-Traversal ist ein Traversal, der jeden Knoten in einem Binärbaum besucht

Die Tiefensuche ist eine Suche. Sie umgeht einen beliebigen Graphen, der nach einem bestimmten Knoten sucht (dass es in einem nicht zyklischen Graphen (auch bekannt als Baum) am besten funktioniert, ist irrelevant).

Dies allein ist groß genug, um sie als Differenznamen zu bezeichnen

Ratschenfreak
quelle
1
+1, aber ich möchte hinzufügen, dass Durchquerungen vor und nach der Bestellung nur Sonderfälle der allgemeineren DFS-Strategie sind.
Frank
1
Bedeutet das Vorbestellen von Traversal nicht einfach, Knoten vor ihren Kindern zu verarbeiten? Wo steht, dass die Knoten einen Binärbaum oder sogar einen Baum bilden?
Kilian Foth
@KilianFoth Ich würde erwarten, dass die Implikation eines Knotens mit Kindern (im Gegensatz zu Nachbarn) eine Baumstruktur impliziert, da dies eine Hierarchie von Knoten vorschlägt. Die Spitze der Hierarchie ist die Wurzel des Baums. Aber ich kann mir vorstellen, dass das Durchlaufen von Vorbestellungen und Nachbestellungen für jeden Baum sinnvoll ist, auch für solche, die nicht binär sind.
YoungJohn
1

Ja, aber es sollte umgekehrt sein: DFSist ähnlich wie PreOrder.
Der Begriff PreOrderist für binäre Bäume und Parser relevanter .
Es ist mit anderen Traversal Aufträge eines binären Baum vergleichen verwendet: InOrder, PostOrderund PreOrder.
Die topologische Sortierung ähnelt der Nachbestellungsdurchquerung (schieben Sie den Knoten nach dem Besuch aller benachbarten Knoten in den Stapel).

user640554
quelle
Meine Gedanken ähneln dieser Antwort. Insbesondere ist eine Vorbestellung eine spezifische Implementierung der übergeordneten Kategorie von DFS. Die Kinderdurchquerung vorbestellt ist starr links und rechts; Während für die generische (übergeordnete) DFS die Durchlaufreihenfolge der Kinder nicht definiert ist und eine beliebige Reihenfolge sein kann.
Jerred S.
-1

Um einen Binärbaum in Preorder zu durchlaufen, werden folgende Operationen ausgeführt

  1. Besuchen Sie die Wurzel
  2. Durchquere den linken Teilbaum
  3. Durchquere den rechten Teilbaum

Das heißt, im folgenden Bild wäre die Vorbestellungsdurchquerung 1,2,3,6,4,5,7,8,9,10,11,12

Im gleichen Bild wäre 1,2,3,4,5,6,7,8,9,10,11,12 für die DFS

DFS-Quelle: http://datastructuresnotes.blogspot.in/2009/02/binary-tree-traversal-preorder-inorder.html

Vorbestellungsquelle: Wiki

DFS

Zedaiq
quelle
9
Dies ist kein Binärbaum. Es ist ein Baum, aber nicht binär.
Manoj R
Was passiert, wenn "6" Unterknoten hat?
Marjan Venema
Sie fragen nach DFS oder Vorbestellung?
Zedaiq
@ManojR Habe es von der oben genannten Quelle.
Zedaiq
Vorbestellung in dieser Grafik gibt die gleiche Antwort
Charles Chow