Baumdurchquerung (Inorder, Preorder, Postorder)

Was ist Tree Traversal?

In der Baumdatenstruktur bedeutet Traversierung das Besuchen von Knoten auf eine bestimmte Weise. Es gibt zwei Arten der Traversierung. Im Allgemeinen basiert diese Art der Traversierung auf dem Binärbaum. Ein Binärbaum bedeutet, dass jeder Knoten maximal zwei Unterknoten haben kann.

Ein Binärbaum ist eine bekannte Datenstruktur. Es gibt auch einen binären Suchbaum (BST). Diese Art der Durchquerung wird für verschiedene Zwecke verwendet. Der Level-Order-Traversal wird zur Berechnung der Tiefe zwischen zwei Knoten verwendet. Es gibt eine andere Baumart namens „AVL“, bei der die Berechnung der Höhe eines Knotens erforderlich ist. Wir können einen Binärbaum im Array darstellen, aber zur Speicheroptimierung verwenden wir Struktur und Zeiger für die Referenzierung des nächsten Knotens.

Arten der Baumdurchquerung

Wie wir besprochen haben binäre Bäume, diskutieren wir nun die einzelnen Arten von Durchquerungen. Je nach Typ gibt es zwei Arten der Durchquerung. Zuvor haben wir die Notwendigkeit der Ebenenreihenfolge oder der Breiten-zuerst-Durchquerung erwähnt. Jetzt Tiefendurchquerung So wird beispielsweise die Post-Order zum Löschen eines Knotens verwendet (darauf werden wir später noch näher eingehen), die Pre-Order wird zum Kopieren eines Binärbaums verwendet und „Inorder“ durchläuft den Baum in nicht abnehmender Reihenfolge.

• Breite-Erste-Durchquerung
• Tiefendurchquerung
• Durchquerung der Vorbestellung
• Post-Order-Traversal
• In-Order-Traversal

Breite-Erste-Durchquerung

Es wird auch als Level-Order-Traversierung bezeichnet. Betrachten wir den folgenden Baum zur Demonstration der Level-Order-Traversierung.

Wir beginnen also mit dem Wurzelknoten „1“. Es wird als Ebene 1 markiert. Dann geht der Algorithmus zu allen untergeordneten Knoten des aktuellen Knotens. Wir werden jetzt Knoten 2 und 3 besuchen. Sie werden als Level 2 gekennzeichnet.

Da wir danach 2 Knoten in Level 2 haben, werden wir auch deren Kinder besuchen. Also besuchen wir 5,6,8,7 und markieren sie als Level 3. Hier ist etwas, das nicht erwähnt wird:

Ebene des Knotens = Ebene des übergeordneten Knotens + 1

Stufe 1: 1

Stufe 2: 2 3

Stufe 3: 5 6 8 7

Ein ähnlicher Algorithmus wird für das BFS verwendet (Breitensuche).

Hier ist der Pseudocode für das Durchlaufen der Ebenenreihenfolge:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

Inorder-Traversierung Binärbaum

Nehmen wir das gleiche Beispiel wie zuvor. Bei dieser Art der Durchquerung besuchen wir zuerst den linken Teilbaum, dann die Wurzel und danach den rechten Teilbaum. Um es leichter zu merken, können wir sagen, dass die Reihenfolge wie folgt lautet: links-wurzel-rechts.

Nehmen wir für den gesamten Baum an, dass die Wurzel 1 ist. Nun folgt der Algorithmus:

• Besuchen Sie den linken Teilbaum von Knoten 1.
• Der aktuelle Knoten ist 2 (da es sich um den linken Teilbaum von 1 handelt)

• Besuchen Sie den linken Teilbaum von 2. Der aktuelle Knoten ist dieses Mal 5.
• Beim Übergang zu 5 gibt es keine untergeordneten Knoten, daher wird Knoten 5 als besucht markiert. Es kehrt zum übergeordneten Knoten zurück. Das ist 2.
• Da der linke Teilbaum von 2 besucht wird, wird nun auch 2 besucht.
• Das Algorithmus verschiebt den aktuellen Knoten in den rechten Teilbaum von Knoten 2, also Knoten 6. Nach dem Besuch von Knoten 6 wird er zu seinem übergeordneten Knoten 2 verschoben.
• Da Knoten 2 besucht wird, besuchen wir nun den übergeordneten Knoten von Knoten 2; Das ist Knoten 1.
• Danach besuchen wir den rechten Teilbaum.

Die endgültige Durchquerung sieht also folgendermaßen aus:

InReihenfolge: 5 → 2 → 6 → 1 → 8 → 3 → 7

Hier ist der Pseudocode für die Durchquerung in der richtigen Reihenfolge:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

Dies ist der rekursive Algorithmus für die Inorder-Traversierung. Für die Binärer Suchbaum (BST), Inorder Traversal liefert das sortierte Array von Werten.

Post-Order-Traversal

Bei dieser Durchquerung durchlaufen wir zuerst den Teilbaum ganz links und dann den Teilbaum ganz rechts nach der Wurzel. Alle Durchquerungen erfolgen im Post-Order. Lassen Sie uns ein Beispiel demonstrieren:

Hier gilt für root = 1,

• Wir gehen zuerst zum linken Teilbaum. Die Wurzel wird also 2.
• Dann hat 2 den Teilbaum verlassen, also gehen wir zu Knoten 5. Jetzt ist die Wurzel 5.
• Es gibt keinen linken Teilbaum und auch keinen rechten Teilbaum. Jetzt markieren wir Knoten 5 als besucht und gehen zu seinem übergeordneten Knoten.

• Jetzt ist die Wurzel 2 und ihr linker Teilbaum ist vollständig besucht. Wir bewegen uns nun zu seinem rechten Unterbaum. Die Wurzel wird also 6.
• Da Knoten 6 keinen linken und rechten Teilbaum hat, markieren wir den besuchten Knoten 6 und wechseln zu seinem übergeordneten Knoten 2.
• Jetzt werden sowohl der linke als auch der rechte Teilbaum für Knoten 2 besucht. Er wird ebenfalls als besucht markiert.
• Wir wechseln zum übergeordneten Knoten von Knoten 2, also Knoten 1.
• Der linke Teilbaum wird für Wurzel 1 besucht. Jetzt besuchen wir auf ähnliche Weise den rechten Teilbaum.

Der markierte Kreis ist der rechte Teilbaum. Jetzt werden wir den rechten Teilbaum besuchen, so wie wir den linken Teilbaum besucht haben. Danach besuchen wir den Knoten. Die letzte Durchquerung wird also sein:

PostOrder: 5 → 6 → 2 → 8 → 7 → 3 → 1

Hier ist der Pseudocode für Post-Order-Traversal:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

Traversal vorbestellen

Bei der Vorbestellungsdurchquerung besucht der Algorithmus zuerst den Wurzelknoten und bewegt sich dann zum linken bzw. rechten Teilbaum. Zum besseren Verständnis können wir uns beispielsweise vorbestellte Durchquerungsbesuche vorstellen Wurzel → links-rechts.

Wählen wir also Knoten 1 als Wurzel aus.

• Gemäß dem Algorithmus wird zuerst die Wurzel, dann der linke und dann der rechte Teilbaum ermittelt.
• Also besuchen wir Wurzel 1. Dann gehen wir zu seinem linken Unterbaum. Die Wurzel wird 2.
• Wir besuchen Knoten 2 und gehen zu seinem linken Teilbaum. Die Wurzel wird also zu 3.
• Wir besuchen Knoten 3 und wechseln dann zu seinem übergeordneten Knoten. Nun wird Knoten 2 und sein linker Teilbaum besucht. Zeit, den richtigen Teilbaum zu besuchen.
• Wir gehen zum rechten Teilbaum, die Wurzel wird zu 4. Wir besuchen 4. Da 4 keinen untergeordneten Knoten hat, gehen wir zu seinem übergeordneten Knoten.
• Jetzt ist root 2 und wird zusammen mit seinem linken und rechten Teilbaum besucht. Wir wechseln also zum übergeordneten Knoten. Jetzt wird root zu 1.
• Ebenso besuchen wir den rechten Teilbaum.

Vorbestellung: 1 → 2 → 3 → 4 → 5 → 6 → 7

Hier ist der Pseudocode für die Preorder-Traversierung:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

Umsetzung in Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) >
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

Ausgang:

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Implementierung in C

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

Ausgang:

Inorder traversal: 4 2 5 1 6 3 7
Preorder traversal: 1 2 4 5 3 6 7
Postorder traversal: 4 5 2 6 7 3 1

Implementierung von C++ (Verwendung von std::queue für die Ebenenreihenfolge)

#include <stdio.h>
#include <stdlib.h>
#include<queue>
typedef struct node {
  int value;
  struct node* left;
  struct node* right;
}node;
// Inorder traversal
void InOrder(struct node* root) {
  if (root == NULL) return;
  InOrder(root->left);
  printf("%d ", root->value);
  InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
void LevelOrder(struct node* root){
   std::queue<struct node*> Q;
   Q.push(root);
   while(!Q.empty()){
   struct node* current = Q.front();
   Q.pop();
   printf("%d ",current->value);
 if(current->left)
   Q.push(current->left);
 if(current->right)
   Q.push(current->right);
  }
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = new node();
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Level Order traversal:\t");
  LevelOrder(root);
  printf("\nInorder traversal:\t");
  InOrder(root);
  printf("\nPreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Häufig gestellte Fragen