Traversierungen
Inorder, Preorder und Postorder.
Traversierungen ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Was ist eine Traversierung?
Eine Traversierung ist eine systematische Methode, jeden Knoten eines Baums genau einmal zu besuchen.
Die drei klassischen Tiefensuchreihenfolgen sind In-Order, Pre-Order und Post-Order. Sie unterscheiden sich nur darin, wann der aktuelle Knoten im Verhältnis zu seinen Teilbäumen verarbeitet wird.
In-Order-Traversierung
Bei der In-Order-Traversierung wird zuerst der linke Teilbaum besucht, dann der Knoten und anschließend der rechte Teilbaum.
Bei einem BST werden die Werte dadurch in aufsteigender Reihenfolge ausgegeben. Deshalb ist diese Traversierung für Suchbäume besonders nützlich.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Pre-Order-Traversierung
Bei der Pre-Order-Traversierung wird zuerst der Knoten besucht, dann der linke Teilbaum und anschließend der rechte Teilbaum.
Sie eignet sich zum Kopieren eines Baums oder zum Erzeugen eines Präfixausdrucks, da die Wurzel vor ihren Kindern ausgegeben wird.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Post-Order-Traversierung
Bei der Post-Order-Traversierung werden zuerst beide Teilbäume besucht und zuletzt der Knoten selbst.
Da die Kinder vor ihrem übergeordneten Knoten verarbeitet werden, ist diese Reihenfolge genau richtig, wenn Sie einen Baum freigeben: Ein Knoten wird nie mehr verwendet, nachdem seine Kinder entfernt wurden.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}Das gemeinsame Muster
Alle drei Tiefensuchtraversierungen verwenden dasselbe Grundgerüst: einen NULL-Basisfall, einen rekursiven Aufruf für das linke Kind, einen rekursiven Aufruf für das rechte Kind und einen Besuchsschritt.
Nur die Position des Besuchsschritts bestimmt den Namen der Reihenfolge.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/In-Order gibt sortiert aus
Dieses Programm erstellt einen kleinen BST und führt eine In-Order-Traversierung aus, um die Eigenschaft der sortierten Ausgabe zu demonstrieren.
Die Werte werden unabhängig von der Einfügereihenfolge vom kleinsten zum größten ausgegeben.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7,12};
for(int i=0;i<6;i++) root=insert(root,d[i]);
in_order(root);
printf("\n");
return 0;
}Die drei Reihenfolgen im Vergleich
Für einen Baum mit der Wurzel 10, dem linken Kind 5 und dem rechten Kind 15 unterscheiden sich die Ausgaben:
Pre-Order ergibt 10 5 15. In-Order ergibt 5 10 15. Post-Order ergibt 5 15 10. Die Knotenwerte sind identisch; nur der Zeitpunkt des Besuchs ändert sich.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Level-Order-Traversierung
Die Breitensuche oder Level-Order-Traversierung besucht die Knoten Ebene für Ebene von oben nach unten. Sie ist nicht von Natur aus rekursiv, sondern verwendet eine Warteschlange.
Wir fügen die Wurzel in die Warteschlange ein, entfernen dann wiederholt einen Knoten, geben ihn aus und fügen seine Kinder ein.
void level_order(Node *root) {
if (!root) return;
Node *queue[100];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
Node *n = queue[head++];
printf("%d ", n->value);
if (n->left) queue[tail++] = n->left;
if (n->right) queue[tail++] = n->right;
}
}Traversierungen ermöglichen praktische Aufgaben
Traversierungen sind Vorlagen für jede Operation, die jeden Knoten erreichen muss, nicht nur für die Ausgabe.
Ersetzen Sie den Besuchsschritt durch das Aufsummieren von Werten, das Finden eines Maximums oder das Kopieren von Knoten, erledigt dieselbe Struktur die Aufgabe.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Kosten einer Traversierung
Jede Traversierung besucht jeden Knoten genau einmal und benötigt daher eine Laufzeit proportional zu n, der Anzahl der Knoten.
Die Rekursion benötigt Stapelspeicher proportional zur Höhe des Baums: Bei einem ausgeglichenen Baum ist diese log(n), im schlimmsten Fall n.
Alle drei auf einmal
Dieses Programm gibt für denselben Baum Pre-Order, In-Order und Post-Order aus, damit Sie sie direkt vergleichen können.
Beobachten Sie, wie nur die Position des Ausgabeaufrufs die resultierende Reihenfolge verändert.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }
int main(void){
Node *root = cn(10);
root->left = cn(5); root->right = cn(15);
pre(root); printf("\n");
ino(root); printf("\n");
post(root); printf("\n");
return 0;
}Kurze Überprüfung
Wählen Sie die passende Traversierung für die Aufgabe.
Zusammenfassung
Tiefensuchtraversierungen verwenden dasselbe rekursive Grundgerüst; die Position des Besuchsschritts macht sie zu Pre-Order, In-Order oder Post-Order. In-Order liefert bei einem BST eine sortierte Ausgabe, und Post-Order ist die sichere Reihenfolge zum Freigeben.
Level-Order ist eine Breitensuche und verwendet eine Warteschlange. Alle Traversierungen besuchen jeden Knoten einmal und benötigen O(n) Zeit.
Häufig gestellte Fragen
Ist die Lektion „Traversierungen“ kostenlos?
Ja — der vollständige Text von „Traversierungen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Traversierungen“?
Inorder, Preorder und Postorder. Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um C Academy zu starten?
Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Traversierungen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?
Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.