Suchen und freigeben
Finden Sie Knoten und geben Sie Speicher frei.
Suchen und freigeben ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 4 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.
Suche in einem BST
Die Suche nutzt die Ordnungsregel. An jedem Knoten vergleichen wir das gesuchte Element mit dem Knotenwert und gehen nur in einen der beiden Teilbäume.
Da wir bei jedem Schritt die Hälfte der verbleibenden Knoten verwerfen, hängen die Suchkosten von der Höhe des Baums ab, nicht von seiner Größe.
Rekursive Suche
Die rekursive Suche hat zwei Basisfälle: Ein leerer Teilbaum bedeutet, dass der Wert nicht gefunden wurde, und ein übereinstimmender Wert bedeutet, dass er gefunden wurde.
Andernfalls rufen wir die Funktion abhängig vom Vergleich rekursiv für den linken oder rechten Teilbaum auf.
Node *search(Node *root, int target) {
if (root == NULL || root->value == target)
return root;
if (target < root->value)
return search(root->left, target);
return search(root->right, target);
}Iterative Suche
Die Suche kann auch als einfache Schleife implementiert werden, wodurch der Rekursionsaufwand entfällt.
Wir folgen den Zeigern den Baum hinunter, bis wir das gesuchte Element finden oder am Ende bei NULL ankommen.
Node *search_iter(Node *root, int target) {
while (root != NULL) {
if (target == root->value) return root;
root = (target < root->value)
? root->left : root->right;
}
return NULL; /* not found */
}Suche in Aktion
Dieses Programm erstellt einen BST und sucht nach einem vorhandenen und einem nicht vorhandenen Wert. Für beide wird ausgegeben, ob sie gefunden wurden.
Ein Rückgabewert ungleich NULL bedeutet „gefunden“; NULL bedeutet, dass der Wert nicht im Baum enthalten ist.
#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;
}
Node *search(Node *r,int t){
if(!r||r->value==t) return r;
return t<r->value ? search(r->left,t) : search(r->right,t);
}
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("7:%s 99:%s\n",
search(root,7)?"found":"no",
search(root,99)?"found":"no");
return 0;
}Das Minimum finden
In einem BST ist der kleinste Wert der am weitesten links stehende Knoten: Folgen Sie left, bis es NULL ist.
Entsprechend ist das Maximum der am weitesten rechts stehende Knoten. Diese Hilfsfunktionen sind für das Löschen und für Bereichsabfragen wichtig.
Node *find_min(Node *root) {
if (root == NULL) return NULL;
while (root->left != NULL)
root = root->left;
return root;
}Warum das Freigeben wichtig ist
Jeder Knoten wurde mit malloc angefordert und muss daher mit free wieder freigegeben werden. Wenn Sie das Freigeben vergessen, entsteht ein Speicherleck.
Sie dürfen einen Knoten jedoch nicht freigeben und anschließend seine Zeiger auf die Kindknoten lesen. Daher ist die Reihenfolge des Freigebens entscheidend.
In Post-Order freigeben
Die sichere Methode zum Freigeben eines Baums ist Post-Order: Geben Sie zuerst beide Kinder und anschließend den Knoten selbst frei.
So wird garantiert, dass die Zeiger left und right eines Knotens gelesen werden, bevor der Speicher dieses Knotens freigegeben wird.
void free_tree(Node *root) {
if (root == NULL) return;
free_tree(root->left);
free_tree(root->right);
free(root);
}Eine gefährliche falsche Reihenfolge
Wenn Sie den Knoten freigeben, bevor Sie rekursiv in seine Kinder wechseln, entsteht undefiniertes Verhalten: Um die Teilbäume zu erreichen, würden Sie auf freigegebenen Speicher zugreifen.
Dies ist ein klassischer Use-after-Free-Fehler. Geben Sie die Kinder immer zuerst frei.
/* WRONG: use-after-free */
void bad_free(Node *root) {
if (!root) return;
free(root); /* freed here */
bad_free(root->left); /* reads freed memory! */
bad_free(root->right);
}Dangling Pointer vermeiden
Nach der Rückkehr von free_tree enthält der ursprüngliche Wurzelzeiger weiterhin die alte Adresse, aber der Speicher ist nicht mehr vorhanden.
Wenn Sie ihn im aufrufenden Code wieder auf NULL setzen, verhindern Sie die versehentliche Wiederverwendung eines Dangling Pointers.
free_tree(root);
root = NULL; /* avoid a dangling pointer */Freigegebene Knoten zählen
Wir können überprüfen, ob das Freigeben funktioniert, indem wir während des Post-Order-Durchlaufs die Knoten zählen und anschließend jeden einzelnen freigeben.
Dieses Programm erstellt einen Baum, gibt ihn frei und meldet, wie viele Knoten freigegeben wurden.
#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;
}
int free_count(Node *r){
if(!r) return 0;
int c = free_count(r->left) + free_count(r->right);
free(r);
return c + 1;
}
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("freed=%d\n", free_count(root));
root = NULL;
return 0;
}Suchen und Freigeben zusammen
Ein vollständiger Lebenszyklus: Erstellen Sie den Baum, durchsuchen Sie ihn und geben Sie ihn anschließend frei. Wenn Sie alle drei Schritte ausführen, bleiben Programme korrekt und frei von Speicherlecks.
Tools wie Valgrind können bestätigen, dass jedem malloc ein free zugeordnet ist.
/* lifecycle
* 1. insert values (allocate)
* 2. search as needed (read-only)
* 3. free_tree(root) (deallocate)
* 4. root = NULL (avoid dangling)
*/Kurze Überprüfung
Denken Sie über sicheres Freigeben nach.
Zusammenfassung
Bei der BST-Suche wird verglichen und pro Schritt in einen Teilbaum abgestiegen; die benötigte Zeit ist proportional zur Höhe. Das Minimum ist der am weitesten links stehende Knoten, das Maximum der am weitesten rechts stehende.
Geben Sie einen Baum in Post-Order frei, damit die Kinder vor dem übergeordneten Knoten freigegeben werden, und setzen Sie anschließend die Wurzel auf NULL, um einen Dangling Pointer zu vermeiden.
Häufig gestellte Fragen
Ist die Lektion „Suchen und freigeben“ kostenlos?
Ja — der vollständige Text von „Suchen und freigeben“ 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 „Suchen und freigeben“?
Finden Sie Knoten und geben Sie Speicher frei. 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 4 von 4.
Wie lange dauert die Lektion „Suchen und freigeben“?
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