Frage Ist Pre-Order Traversal auf einem Binärbaum wie Depth First Search?


Es scheint mir, als ob Traversierung vor der Order und DFS dieselben sind 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?

Danke im Voraus!


17
2018-02-05 08:08


Ursprung


Antworten:


Pre-Order ist eine Art von DFS.

Es gibt drei Arten von Tiefen-Traversierungen: Vorbestellen, In-Reihenfolge und Nach-Reihenfolge.

Auschecken Hier Für mehr Information.


36
2018-02-05 08:16



Es hängt wahrscheinlich von der Definition und Implementierung der Tiefe ab Algorithmus. Das DefaultMutableTreeNode Klasse des Java Swing's JTree Die Komponente hat die folgenden Aufzählungsmethoden, die für das Traversieren von Bäumen verwendet werden:

  • depthFirstEnumeration ()
  • postorderEnumeration ()
  • preorderEnumeration ()
  • breaththirstEnumeration ()

In Java Swing Implementierung der depthFirstEnumeration ist dasselbe als die postOrderEnumeration. Meine Tests und die offizielle Dokumentation  bestätigt dies.

Andere können definieren, was Tiefen-zuerst anders bedeutet. Zum Beispiel einen Artikel auf Wikipedia gibt an, dass Pre- und Post-Order-Traversale spezifische Typen sind einer Tiefen-zuerst-Traversierung. Dies würde bedeuten, dass die Tiefe zuerst durchlaufen wird ist kein konkreter Traversalalgorithmus.


5
2018-04-16 15:20



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.


5
2017-12-20 04:35