Nützlichkeit der Durchquerung von Binärbäumen vor und nach der Bestellung

Das mag sehr naiv sein, aber ich habe mich gefragt, ob es sich um den Kontext von binären Bäumen (einfach, sortiert und ausgeglichen) aller Traversaltypen handelt:

• Tiefen-Vorbestellung
• Tiefe zuerst in der Reihenfolge
• Tiefe zuerst nachbestellen
• Breite zuerst

Was ist der eigentliche Nutzen von Vor- und Nachbestellungen? Ich meine, gibt es einen Typ und / oder eine Konfiguration eines Binärbaums, bei dem das Durchlaufen vor und / oder nach der Bestellung einen Vorteil gegenüber den beiden anderen bietet?

AFAICS, es gibt bestimmte Typen und Konfigurationen von Binärbäumen, für die In-order und Width-First einen bestimmten Vorteil bieten könnten:

• Für einen ausgeglichenen Binärbaum wird bei jedem Durchlaufen der Tiefe zuerst weniger Speicherplatz benötigt als bei einem Durchlaufen der Breite zuerst 2 Knoten zu einem bestimmten Zeitpunkt, während die letzte Ebene 3 oder 4 Knoten hat, so dass der erste Durchlauf zu einem bestimmten Zeitpunkt bis zu 3 oder 4 Knoten speichern müsste. In diesem Fall wird bei der Verwendung von In-Order-Traversal am wenigsten Speicherplatz benötigt und die Knoten werden in ihrer natürlichen Reihenfolge besucht.

• Für einen nicht ausgeglichenen Binärbaum würde, wenn er sich dem Einfügeszenario des schlechtesten Falls nähert, ein Durchlaufen mit der Breite zuerst weniger Speicherplatz verbrauchen als bei allen Durchläufen mit der Tiefe zuerst. In diesem Fall bietet die Breite zuerst einen Vorteil. In-Order-Traversal hat wiederum den Vorteil, Werte in ihrer natürlichen Reihenfolge zu besuchen.

Ich kann mir jedoch keine Situation vorstellen, in der Vor- und Nachhinein einen Vorteil gegenüber den beiden anderen bieten würden.

Sie müssen verschiedene Dinge mit Bäumen tun, wie das Übersetzen zwischen der Datenstruktur und einer seriellen Darstellung, wie in einer Datei oder in einer Sprache.

Angenommen, Sie haben einen Analysebaum wie diesen:

    *
   / \
  +   \
 / \   \
A   B   C

Sie können es serialisieren, * + A B Cindem Sie es in der Präfix-Reihenfolge oder A B + C *in der Postfix-Reihenfolge durchlaufen. Wenn Sie überhaupt mit Sprachprozessoren arbeiten, müssen solche Dinge selbstverständlich sein.

Der Wikipedia-Artikel enthält eine kurze Beschreibung, wann Sie die verschiedenen Arten der Tiefensuche verwenden möchten:

• Durch Vorbestellen des Durchlaufs beim Duplizieren von Knoten und Werten kann ein vollständiges Duplikat eines Binärbaums erstellt werden. Es kann auch verwendet werden, um einen Präfixausdruck (polnische Notation) aus Ausdrucksbäumen zu erstellen: Durchlaufen Sie den Ausdrucksbaum vorab.
• In-Order-Traversal wird sehr häufig für binäre Suchbäume verwendet, da es dem Komparator zufolge, der den binären Suchbaum (daher der Name) eingerichtet hat, Werte aus der zugrunde liegenden Menge in der angegebenen Reihenfolge zurückgibt.
• Nachträgliches Durchlaufen beim Löschen oder Freigeben von Knoten und Werten kann einen gesamten Binärbaum löschen oder freigeben. Es kann auch eine Postfix-Darstellung eines Binärbaums generieren.

Es läuft auf die logistischen Anforderungen eines Algorithmus hinaus. Wenn Sie beispielsweise beim Löschen keine Nachbestellungsüberquerung verwenden, verlieren Sie die Referenzen, die Sie zum Löschen der untergeordneten Bäume benötigen.

Der Sinn verschiedener Algorithmen für den Umgang mit binären Bäumen besteht nicht darin, Dinge mit Bäumen zu tun. Auf dieser abstrakten Ebene ist eine Reihenfolge so gut wie jede andere, da Sie nur abstrakte Symbole aus der Prozedur erhalten.

Aber normalerweise werden Bäume zur Darstellung verwendet interessante Dinge , und das kann einen großen Unterschied im Ergebnis bewirken. Wenn die Knoten beispielsweise Suchzustände in einer vollständigen Suche in einer großen Domäne (möglicherweise sogar in einer unendlichen Domäne) darstellen, bestimmt die Reihenfolge, in der die Ergebnisse gefunden werden, nicht nur, in welcher Reihenfolge, sondern auch, ob dies jemals der Fall sein wird finde überhaupt keine Lösungen . Der Punkt ist bei unendlichen Domänen am einfachsten zu erkennen: Wenn Sie unachtsam absteigen, übersehen Sie möglicherweise eine Lösung, die ganz oben im Baum liegt, einfach, weil Sie eine falsche Wendung eingeschlagen haben. In der Praxis gilt dies jedoch auch für Domänen, die einfach sehr groß und nicht wirklich unendlich sind, da Speicher und Festplatten ebenfalls endlich sind.