Baumknoten und Struktur
Modellieren Sie einen Knoten mit Zeigern.
Baumknoten und Struktur ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 1 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 ein Binärbaum?
Ein Binärbaum ist eine hierarchische Struktur, in der jeder Knoten einen Wert und Verweise auf bis zu zwei Kindknoten enthält: einen linken und einen rechten.
Der oberste Knoten ist die Wurzel. Knoten ohne Kinder sind Blätter. Diese Struktur macht Binärbäume besonders geeignet für schnelles Suchen, Sortieren und rekursive Verarbeitung.
Die Node-Struct
In C modellieren wir einen Knoten mit einer Struct, die neben den Daten zwei selbstreferenzierende Pointer speichert.
Jeder Pointer zeigt entweder auf einen weiteren Node oder auf NULL, wenn auf dieser Seite kein Kind vorhanden ist.
struct Node {
int value;
struct Node *left;
struct Node *right;
};Warum selbstreferenzierende Pointer?
Ein Knoten kann keinen vollständigen Knoten als Wert enthalten, da dies unendlich viel Speicher erfordern würde. Stattdessen enthält er Pointer auf seine Kinder.
Pointer haben eine feste Größe. Dadurch bleibt die Struct von bekannter Größe und kann dennoch mit weiteren Knoten auf dem Heap verknüpft werden.
struct Node {
int value;
struct Node *left; /* 8 bytes on 64-bit */
struct Node *right; /* 8 bytes on 64-bit */
};Ein typedef zur Vereinfachung
struct Node überall auszuschreiben, ist umständlich. Mit einem typedef können wir einfach Node schreiben.
Innerhalb der Struct wird das Tag weiterhin benötigt, da der Typ an dieser Stelle noch nicht vollständig definiert ist.
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;Einen Node allokieren
Knoten liegen auf dem Heap und werden mit malloc erstellt. Wir setzen den Wert und initialisieren beide Kinder-Pointer auf NULL.
Prüfen Sie immer, dass malloc nicht NULL zurückgegeben hat, bevor Sie den Speicher verwenden.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (n == NULL) return NULL;
n->value = value;
n->left = NULL;
n->right = NULL;
return n;
}Einen kleinen Baum von Hand aufbauen
Um die Verknüpfungen zu verstehen, verbinden wir drei Knoten manuell: eine Wurzel mit zwei Kindern.
Dieses Programm erstellt den Baum und gibt die Werte aus; anschließend würden wir ihn normalerweise freigeben (das wird später behandelt).
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;
Node *create_node(int v) {
Node *n = malloc(sizeof(Node));
n->value = v; n->left = NULL; n->right = NULL;
return n;
}
int main(void) {
Node *root = create_node(10);
root->left = create_node(5);
root->right = create_node(15);
printf("%d %d %d\n", root->left->value, root->value, root->right->value);
return 0;
}Enkelknoten erreichen
Sie navigieren im Baum, indem Sie den Pfeiloperator verkettet verwenden. root->left->right führt zum linken Kind und anschließend zu dessen rechtem Kind.
Bevor Sie einem Pointer folgen, stellen Sie sicher, dass er nicht NULL ist, sonst stürzt Ihr Programm ab.
/* root
* \
* right (15)
* \
* right->right (20)
*/
if (root->right != NULL && root->right->right != NULL)
printf("%d\n", root->right->right->value);Knoten rekursiv zählen
Rekursion eignet sich auf natürliche Weise für Bäume. Um Knoten zu zählen, gilt: Ein leerer Teilbaum enthält null Knoten; andernfalls zählen Sie den aktuellen Knoten und beide Teilbäume.
Die NULL-Prüfung ist der Basisfall, der die Rekursion beendet.
int count_nodes(Node *root) {
if (root == NULL) return 0;
return 1 + count_nodes(root->left)
+ count_nodes(root->right);
}Die Höhe messen
Die Höhe eines Baums ist der längste Weg von der Wurzel zu einem Blatt, gemessen in Kanten.
Wir nehmen die größere der beiden Teilbaumhöhen und addieren eins. Ein leerer Baum erhält die Höhe -1, sodass ein einzelner Knoten die Höhe 0 hat.
int height(Node *root) {
if (root == NULL) return -1;
int l = height(root->left);
int r = height(root->right);
return 1 + (l > r ? l : r);
}Blätter erkennen
Ein Blatt ist ein Knoten ohne Kinder: Sowohl left als auch right sind NULL.
Diese kleine Hilfsfunktion ist in vielen Traversierungs- und Zählroutinen nützlich.
int is_leaf(Node *n) {
return n != NULL && n->left == NULL && n->right == NULL;
}Die Struktur einsetzen
Hier wird ein kleiner Baum erstellt, und wir geben seine Knotenzahl und Höhe mithilfe der rekursiven Hilfsfunktionen aus.
Beachten Sie, dass die Hilfsfunktionen keine feste Form voraussetzen. Sie funktionieren für jeden Baum, weil die Rekursion den tatsächlichen Pointern folgt.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }
int main(void){
Node *root = nn(10);
root->left = nn(5); root->right = nn(15);
root->left->left = nn(2);
printf("nodes=%d height=%d\n", count(root), height(root));
return 0;
}Kurzer Test
Testen Sie Ihr Verständnis der Knotenstruktur.
Zusammenfassung
Ein Binärbaumknoten enthält einen Wert und zwei selbstreferenzierende Pointer (left, right), die bei fehlenden Kindern auf NULL gesetzt werden.
Wir allokieren Knoten mit malloc, verknüpfen sie manuell und verarbeiten sie rekursiv. Die NULL-Prüfung ist immer der Basisfall für Zählungen, Höhenberechnungen und Blatttests.
Häufig gestellte Fragen
Ist die Lektion „Baumknoten und Struktur“ kostenlos?
Ja — der vollständige Text von „Baumknoten und Struktur“ 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 „Baumknoten und Struktur“?
Modellieren Sie einen Knoten mit Zeigern. 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 1 von 4.
Wie lange dauert die Lektion „Baumknoten und Struktur“?
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.
Alle Lektionen in diesem Kurs
- Baumknoten und Struktur
- In einen BST einfügen
- Traversierungen
- Suchen und freigeben