Binärbaum-Traversal

1. Binärbaum-Traversal
2. Abbildung der Binärbaum-Traversal
3. Binärbaum-Traversal-Algorithmus
4. Implementierung von Binärbaum-Traversalen
5. Binärbaum-Traversal-Algorithmus Komplexität

Ein Binärbaum ist eine nichtlineare Datenstruktur. Er wird als Binärbaum bezeichnet, weil jeder Knoten maximal zwei Kinder hat. Diese Kinder werden als linke Kinder und rechte Kinder bezeichnet. Er kann auch als ein ungerichteter Graph interpretiert werden, in dem der oberste Knoten als Wurzel bezeichnet wird. Im Gegensatz zu linearen Datenstrukturen, die nur auf eine Weise durchlaufen werden können, kann ein Baum auf verschiedene Arten durchlaufen werden. Wir können einen Baum traversieren, indem wir ihn entlang der Tiefe oder der Breite erkunden. Der erste Ansatz wird als Tiefen-Erste-Durchquerung bezeichnet, der zweite als Breite-Erste-Durchquerung. In diesem Artikel werden wir die Tiefenüberquerungen besprechen.

Es gibt 3 Arten von Tiefenüberquerungen - Inorder, Preorder und Postorder. Wir werden jede von ihnen einzeln besprechen.

Binärbaum-Traversal

Inorder-Traversal

Bei diesem Traversal wird zuerst der linke Teilbaum, dann die Wurzel und zuletzt der rechte Teilbaum besucht. Jeder Knoten ähnelt einem Teilbaum. Bei BST liefert die Inorder-Traversierung alle Elemente in aufsteigender Reihenfolge

Preorder-Traversal

Bei diesem Traversal wird zuerst die Wurzel, dann der linke Teilbaum und zuletzt der rechte Teilbaum besucht. Jeder Knoten ähnelt einem Teilbaum. Er wird normalerweise verwendet, um zu replizieren, d. h. eine Kopie des Baums zu erstellen. Präfix-Traversal hilft auch dabei, aus einem Ausdrucksbaum einen Präfix-Ausdruck zu erzeugen.

Postorder-Traversal

Bei dieser Traversierung wird zuerst der linke Teilbaum, dann der rechte Teilbaum und zuletzt die Wurzel besucht. Jeder Knoten ähnelt einem Teilbaum. Sie wird verwendet, um Bäume effektiv zu löschen. Es hilft auch dabei, Postfix-Ausdrücke aus einem Ausdrucksbaum zu erzeugen.

Abbildung der Binärbaum-Traversal

Inorder-Traversal: (4, 2, 1, 5, 3, 6, 7, 8, 9)

Wir rufen Inorder-Traversal auf dem Wurzelknoten 3 auf. Wir traversieren rekursiv nach links, um den Knoten 4 zu erreichen, der der am weitesten links liegende Knoten ist, und schließen ihn in unsere Ausgabe ein; da er die Wurzel ist und keinen linken Knoten hat, besuchen wir seinen am weitesten rechts liegenden Knoten 2 und schließen ihn in unsere Traversierung ein. Auf diese Weise durchlaufen wir den gesamten Baum, um die obige Reihenfolge als unsere Ausgabe zu erhalten.

Vorordnungstraversal: (3, 1, 4, 2, 5, 7, 6, 9, 8)

Wir rufen den Preorder-Traversal auf dem Wurzelknoten 3 auf und nehmen ihn in unsere Ausgabe auf. Dann traversieren wir rekursiv nach links, um den nächsten Wurzelknoten 1 und anschließend 4 zu erreichen. Da 4 kein linkes Kind hat, besuchen wir den rechten Knoten 2. Jetzt haben wir den Teilbaum unter dem Wurzelknoten 4 abgedeckt und wir traversieren zurück zum Knoten 1 und gehen nach rechts zu dessen Knoten 5. Auf diese Weise durchlaufen wir den gesamten Baum, um die obige Reihenfolge als unsere Ausgabe zu erhalten.

Postorder-Traversal: (2, 4, 5, 1, 6, 8, 9, 7, 3)

Wir rufen das Postorder-Traversal auf dem Wurzelknoten 3 auf und traversieren rekursiv nach links bis zum Knoten 4. Bevor wir 4 in unser Traversal aufnehmen, müssen wir seinen rechten Knoten 2 besuchen. Wir schließen 2 und dann 4 in unsere Ausgabe ein und gehen zurück zu 1. 1 hat seinen rechten Knoten 5 nicht besucht, also schließen wir zuerst 5 und dann 1 in die Ausgabe ein. Dann gehen wir zurück zum Wurzelknoten 3 und fahren mit dem Traversieren des rechten Teilbaums fort. Auf diese Weise durchlaufen wir den gesamten Baum, um die obige Reihenfolge als Ausgabe zu erhalten.

Binärbaum-Traversal-Algorithmus

Traversal in Reihenfolge

Traversal vor der Reihenfolge

Postorder-Traversal

Implementierung von Binärbaum-Traversalen

#include <iostream>
using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
  Node(int x) {
    this->key = x;
    this->left = this->right = NULL;
  }
};

void inorder(Node* root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}
void preorder(Node* root) {
  if (root != NULL) {
    cout << root->key << " ";
    preorder(root->left);
    preorder(root->right);
  }
}

void postorder(Node* root) {
  if (root != NULL) {
    postorder(root->left);
    postorder(root->right);
    cout << root->key << " ";
  }
}

int main() {
  Node* root = new Node(3);
  root->left = new Node(1);
  root->right = new Node(7);
  root->left->left = new Node(4);
  root->left->right = new Node(5);
  root->left->left->right = new Node(2);
  root->right->left = new Node(6);
  root->right->right = new Node(9);
  root->right->right->left = new Node(8);
  cout << "The inorder traversal of the tree is : ";
  inorder(root);
  cout << endl;
  cout << "The preorder traversal of the tree is : ";
  preorder(root);
  cout << endl;
  cout << "The postorder traversal of the tree is : ";
  postorder(root);
  cout << endl;
}

Binärbaum-Traversal-Algorithmus Komplexität

Zeitkomplexität

• Durchschnittlicher Fall

Es gibt n Knoten in einem Baum, in allen 3 Arten von Traversalen, müssen wir jeden Knoten besuchen. Da wir über n Knoten iterieren, wenn auch in einer anderen Reihenfolge, ist die Zeitkomplexität für alle 3 Traversierungen in der Größenordnung von O(n). Die durchschnittliche Zeitkomplexität ist O(n).

• Bester Fall

Die Zeitkomplexität im besten Fall ist O(n). Sie ist die gleiche wie die durchschnittliche Zeitkomplexität für alle 3 Traversalen.

• Schlechtester Fall

Die Zeitkomplexität im ungünstigsten Fall ist O(n). Sie ist identisch mit der Zeitkomplexität im schlimmsten Fall für alle 3-Traversalen.

Raumkomplexität

Die Platzkomplexität des Algorithmus ist O(n) aufgrund des zusätzlichen Platzbedarfs durch Rekursionsaufrufe.