Baumdurchquerung - Inorder, Preorder und Postorder (die drei Hauptdurchquerungen)

Алгоритм, Tree, Дерево

Tree Traversal bedeutet, jeden Knoten im Baum zu besuchen. Sie können beispielsweise alle Werte zum Baum hinzufügen oder den größten finden. Für all diese Operationen müssen Sie jeden Knoten des Baums besuchen.

Lineare Datenstrukturen wie Arrays, Stapel, Warteschlangen und verknüpfte Listen haben nur eine Möglichkeit, Daten zu lesen. Aber eine hierarchische Datenstruktur wie ein Baum kann auf viele verschiedene Arten durchlaufen werden.

Denken wir darüber nach, wie wir die Elemente des Baums im oben gezeigten Bild lesen können.

Von oben beginnend, von links nach rechts

1 -> 12 -> 9 -> 5 -> 6

Von unten beginnend, von links nach rechts

5 -> 6 -> 12 -> 9 -> 1

Obwohl dieser Prozess ziemlich einfach ist, berücksichtigt er nicht die Hierarchie des Baums, sondern nur die Tiefe der Knoten.

Stattdessen verwenden wir Traversierungsmethoden, die die zugrunde liegende Struktur des Baums respektieren, d.h.

struct node {
    int data;
    struct node* left;
    struct node* right;
}

Der Strukturknoten, auf den left (links) und right (rechts) zeigen, kann andere linke und rechte Kinder haben, also müssen wir sie als Unterbäume behandeln, nicht als Unterknoten.

Gemäß dieser Struktur ist jeder Baum eine Kombination

• Knoten, der Daten trägt
• Zwei Teilbäume

Denken Sie daran, dass unser Ziel darin besteht, jeden Knoten zu besuchen, also müssen wir alle Knoten im Unterbaum besuchen, den Wurzelknoten besuchen und auch alle Knoten im rechten Unterbaum besuchen.

Abhängig von der Reihenfolge, in der wir es tun, kann es drei Arten von Traversierung geben.

Zentrierter Traversaltyp (Inorder Traversal)

1. Besuchen Sie zunächst alle Knoten im linken Teilbaum
2. Dann der Wurzelknoten
3. Besuchen Sie alle Knoten im rechten Teilbaum

inorder(root->left)
display(root->data)
inorder(root->right)

Direct-Traversal-Typ (Preorder-Traversal)

1. Besuchen Sie den Stammknoten
2. Besuchen Sie alle Knoten im linken Teilbaum
3. Besuchen Sie alle Knoten im rechten Teilbaum

display(root->data)
preorder(root->left)
preorder(root->right)

Postorder-Durchlauf

1. Besuchen Sie alle Knoten im linken Teilbaum
2. Besuchen Sie den Root-Knoten
3. Besuchen Sie alle Knoten im rechten Teilbaum

postorder(root->left)
postorder(root->right)
display(root->data)

Lassen Sie uns den zentrierten Traversierungstyp visualisieren. Beginnen wir mit dem Root-Knoten.

Zuerst durchlaufen wir den linken Teilbaum. Wir müssen auch daran denken, den Wurzelknoten und den rechten Teilbaum zu besuchen, wenn der Baum fertig ist.

Legen wir alles auf einen Stapel, damit wir uns erinnern.

Lassen Sie uns nun zu dem Teilbaum übergehen, der oben auf dem Stapel angegeben ist.

Wieder folgen wir der gleichen Regel des zentrierten Typs (inorder)

Left subtree -> root -> right subtree

Nachdem wir den linken Teilbaum durchlaufen haben, bleibt uns übrig

Da Knoten "5" keine Unterbäume hat, drucken wir ihn direkt aus. Danach drucken wir seinen übergeordneten Knoten „12“ und dann seinen rechten untergeordneten Knoten „6“.

Es war nützlich, alles auf den Stapel zu legen, denn jetzt, da der linke Teilbaum des Wurzelknotens durchlaufen wurde, können wir ihn ausdrucken und zum rechten Teilbaum weitergehen.

Nachdem Sie alle Elemente durchlaufen haben, sieht der zentrierte Traversaltyp (inorder Traversal) folgendermaßen aus:

5 -> 12 -> 6 -> 1 -> 9

Wir müssen den Stapel nicht selbst erstellen, da die Rekursion die richtige Reihenfolge für uns beibehält.

Der vollständige Code für zentrierten (inorder), direkten (preorder) und umgekehrten (postorder) Traversaltyp in der Programmiersprache C ist unten:

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node* left;
    struct node* right;
};

void inorder(struct node* root){
    if(root == NULL) return;
    inorder(root->left);
    printf("%d ->", root->data);
    inorder(root->right);
}

void preorder(struct node* root){
    if(root == NULL) return;
    printf("%d ->", root->data);
    preorder(root->left);
    preorder(root->right);
}

void postorder(struct node* root) {
    if(root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ->", root->data);
}


struct node* createNode(value){
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

struct node* insertLeft(struct node *root, int value) {
    root->left = createNode(value);
    return root->left;
} 


struct node* insertRight(struct node *root, int value){
    root->right = createNode(value);
    return root->right;
}


int main(){
    struct node* root = createNode(1);
    insertLeft(root, 12);
    insertRight(root, 9);

    insertLeft(root->left, 5);
    insertRight(root->left, 6);

    printf("Inorder traversal \n");
    inorder(root);

    printf("\nPreorder traversal \n");
    preorder(root);

    printf("\nPostorder traversal \n");
    postorder(root);
}

Die Ausgabe des Codes sieht folgendermaßen aus:

Inorder traversal                                                                                                                                                         
5 ->12 ->6 ->1 ->9 ->                                                                                                                                                     
Preorder traversal                                                                                                                                                        
1 ->12 ->5 ->6 ->9 ->                                                                                                                                                     
Postorder traversal                                                                                                                                                       
5 ->6 ->12 ->9 ->1 ->