webentwicklung-frage-antwort-db.com.de

Verwendungszweck der binären Suchbaum-Traversalstrategien Preorder, Postorder und Inorder

Ich habe kürzlich festgestellt, dass ich, obwohl ich in meinem Leben viel von BST verwendet habe, noch nie darüber nachgedacht habe, etwas anderes als Inorder Traversal zu verwenden (obwohl ich weiß und weiß, wie einfach es ist, ein Programm für die Verwendung von Pre-/Post-Order-Traversal anzupassen).

Als ich das bemerkte, zog ich einige meiner alten Lehrbücher für Datenstrukturen heraus und suchte nach Begründungen für die Nützlichkeit von Traversen vor und nach der Bestellung - sie sagten jedoch nicht viel.

Was sind einige Beispiele für die praktische Verwendung von Preorder/Postorder? Wann ist es sinnvoller als in-order?

Wann ist die Traversal-Strategie für Pre-Order, In-Order und Post-Order anzuwenden?

Bevor Sie verstehen können, unter welchen Umständen Pre-Order, In-Order und Post-Order für einen Binärbaum zu verwenden sind, müssen Sie genau verstehen, wie jede Traversierungsstrategie funktioniert. Verwenden Sie den folgenden Baum als Beispiel.

Die Wurzel des Baumes ist 7, der am weitesten links liegende Knoten ist , der am weitesten rechts liegende Knoten ist 1.

enter image description here

Traversal vorbestellen:

Zusammenfassung: Beginnt an der Wurzel (7) und endet am Knoten ganz rechts (1)

Durchlaufreihenfolge: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

In-order Traversal:

Zusammenfassung: Beginnt am äußersten linken Knoten () und endet am äußersten rechten Knoten (1)

Durchlaufsequenz: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Nachbestellungsdurchquerung:

Zusammenfassung: Beginnt mit dem Knoten ganz links () und endet mit der Wurzel (7)

Durchlaufreihenfolge: 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Wann ist Pre-Order, In-Order oder Post-Order zu verwenden?

Die Traversierungsstrategie, die der Programmierer auswählt, hängt von den spezifischen Anforderungen des zu entwerfenden Algorithmus ab. Das Ziel ist die Geschwindigkeit. Wählen Sie also die Strategie, mit der Sie die Knoten erreichen, die Sie am schnellsten benötigen.

  1. Wenn Sie wissen, dass Sie die Wurzeln erforschen müssen, bevor Sie Blätter untersuchen, wählen Sie Vorbestellung, da Sie auf alle Wurzeln vor allen Blättern stoßen.

  2. Wenn Sie wissen, dass Sie alle Blätter vor einem Knoten untersuchen müssen, wählen Sie Nachbestellung, da Sie keine Zeit damit verschwenden, Wurzeln auf der Suche nach Blättern zu untersuchen.

  3. Wenn Sie wissen, dass der Baum eine inhärente Sequenz in den Knoten hat und Sie den Baum wieder in seine ursprüngliche Sequenz reduzieren möchten, sollte ein in-order Traversal verwendet werden. Der Baum würde auf die gleiche Weise abgeflacht, wie er erstellt wurde. Durchlaufen von Vorbestellungen oder Nachbestellungen wird der Baum möglicherweise nicht in die Reihenfolge zurückgeführt, in der er erstellt wurde.

Rekursive Algorithmen für Pre-Order, In-Order und Post-Order (C++):

struct Node{
    int data;
    Node *left, *right;
};
void preOrderPrint(Node *root)
{
  print(root->name);                                  //record root
  if (root->left != NULL) preOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}

void inOrderPrint(Node *root)
{
  if (root.left != NULL) inOrderPrint(root->left);   //traverse left if exists
  print(root->name);                                 //record root
  if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}

void postOrderPrint(Node *root)
{
  if (root->left != NULL) postOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
  print(root->name);                                   //record root
}
111
Eric Leschinski

Wenn ich das hierarchische Format des Baums einfach in einem linearen Format ausdrucken wollte, würde ich wahrscheinlich eine Vorbestellungsüberquerung verwenden. Beispielsweise:

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G
23

Vorbestellung/Bestellung/Nachbestellung Verwendung: Einfache Wörter

Pre-order: Wird zum Erstellen einer Kopie eines Baums verwendet. Beispiel: Wenn Sie eine Replik eines Baums erstellen möchten und Knotenwerte in einem Array benötigen und wenn Sie diese Werte vom Index 0 einfügen, um in a zu enden Neuer Baum, Sie erhalten eine Replik

In-order:: Um die Werte des Knotens in nicht aufsteigender Reihenfolge abzurufen

Nachbestellung:: Wenn Sie einen Baum von Blatt zu Wurzel löschen möchten

22
Viraj Nimbalkar

Pre- und Post-Order beziehen sich auf rekursive Top-Down- bzw. Bottom-Up-Algorithmen. Wenn Sie einen bestimmten rekursiven Algorithmus iterativ in Binärbäume schreiben möchten, tun Sie dies im Wesentlichen.

Beachten Sie außerdem, dass Sequenzen vor und nach der Bestellung den vorliegenden Baum vollständig spezifizieren und eine kompakte Codierung ergeben (zumindest für spärliche Bäume).

4
Raphael

Es gibt Unmengen von Orten, an denen dieser Unterschied eine echte Rolle spielt.

Eine großartige Sache, auf die ich hinweisen möchte, ist die Codegenerierung für einen Compiler. Betrachten Sie die Aussage:

x := y + 32

Die Art und Weise, wie Sie Code dafür generieren würden, ist (natürlich naiv), zuerst Code zum Laden von y in ein Register, zum Laden von 32 in ein Register und dann eine Anweisung zum Hinzufügen der beiden zu generieren. Da sich etwas in einem Register befinden muss, bevor Sie es manipulieren (nehmen wir an, Sie können immer konstante Operanden ausführen, aber was auch immer), müssen Sie dies auf diese Weise tun.

Im Allgemeinen reduzieren sich die Antworten, die Sie auf diese Frage erhalten, im Wesentlichen auf diese Frage: Der Unterschied ist wirklich wichtig, wenn es eine gewisse Abhängigkeit zwischen der Verarbeitung verschiedener Teile der Datenstruktur gibt. Sie sehen dies, wenn Sie die Elemente drucken, wenn Sie Code generieren (der externe Status macht den Unterschied, Sie können dies natürlich auch monadisch anzeigen) oder wenn Sie andere Arten von Berechnungen über die Struktur durchführen, die Berechnungen abhängig von den zuerst verarbeiteten untergeordneten Elementen beinhalten .

1