Zoeken en vrijgeven
Zoek knopen en geef geheugen vrij.
Zoeken en vrijgeven is een gratis C Academy-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject C Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus C Academy bevat in totaal 4 lessen.
Zoeken in een BST
Zoeken maakt gebruik van de ordeningsregel. Bij elk knooppunt vergelijken we het doel met de waarde van het knooppunt en gaan we verder in slechts één deelboom.
Omdat we bij elke stap de helft van de resterende knooppunten weggooien, groeien de zoekkosten mee met de hoogte van de boom, niet met de omvang ervan.
Recursief zoeken
Recursief zoeken heeft twee basissituaties: een lege deelboom betekent dat de waarde niet is gevonden en een overeenkomende waarde betekent dat deze wel is gevonden.
Anders gaan we afhankelijk van de vergelijking recursief naar links of naar rechts.
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);
}Iteratief zoeken
Zoeken kan ook met een eenvoudige lus, zodat de overhead van recursie wordt vermeden.
We volgen de verwijzingen door de boom totdat we het doel vinden of bij NULL aan het einde komen.
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 */
}Zoeken in actie
Dit programma bouwt een BST en zoekt naar een aanwezige en een afwezige waarde. Daarna drukt het af of elke waarde is gevonden.
Een retourwaarde die niet NULL is betekent dat de waarde is gevonden; NULL betekent dat de waarde niet in de boom staat.
#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;
}Het minimum vinden
In een BST is de kleinste waarde het meest linkse knooppunt: volg left steeds totdat het NULL is.
Op dezelfde manier is het maximum het meest rechtse knooppunt. Deze hulpfuncties zijn belangrijk voor verwijderen en bereikquery's.
Node *find_min(Node *root) {
if (root == NULL) return NULL;
while (root->left != NULL)
root = root->left;
return root;
}Waarom vrijgeven belangrijk is
Elk knooppunt komt uit malloc, dus elk knooppunt moet met free worden teruggegeven. Als je vergeet geheugen vrij te geven, ontstaat er een geheugenlek.
Je kunt een knooppunt echter niet vrijgeven en daarna nog de verwijzingen naar zijn kinderen lezen. Daarom is de volgorde van vrijgeven cruciaal.
Vrijgeven in navolgende volgorde
De veilige manier om een boom vrij te geven is in navolgende volgorde: geef eerst beide kinderen vrij en daarna het knooppunt zelf.
Zo weet je zeker dat je de verwijzingen left en right van een knooppunt leest voordat het geheugen van dat knooppunt wordt vrijgegeven.
void free_tree(Node *root) {
if (root == NULL) return;
free_tree(root->left);
free_tree(root->right);
free(root);
}Een gevaarlijke verkeerde volgorde
Als je het knooppunt vrijgeeft voordat je recursief naar de kinderen gaat, ontstaat ongedefinieerd gedrag: je zou vrijgegeven geheugen derefereren om de deelbomen te bereiken.
Dit is een klassieke fout waarbij geheugen na vrijgave wordt gebruikt. Geef altijd eerst de kinderen vrij.
/* 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);
}Zwevende verwijzingen voorkomen
Nadat free_tree is teruggekeerd, bevat de oorspronkelijke verwijzing naar de wortel nog steeds het oude adres, maar het geheugen bestaat niet meer.
Door deze in de aanroeper terug te zetten naar NULL, voorkom je per ongeluk hergebruik van een zwevende verwijzing.
free_tree(root);
root = NULL; /* avoid a dangling pointer */Vrijgegeven knooppunten tellen
We kunnen bevestigen dat vrijgeven werkt door tijdens de doorloop in navolgende volgorde de knooppunten te tellen en ze daarna één voor één vrij te geven.
Dit programma bouwt een boom, geeft deze vrij en meldt hoeveel knooppunten zijn vrijgegeven.
#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;
}Zoeken en vrijgeven samen
Een volledige levenscyclus: bouw de boom, zoek erin en geef hem daarna vrij. Door alle drie te doen blijven programma's correct en vrij van geheugenlekken.
Hulpmiddelen zoals Valgrind kunnen bevestigen dat elke aanroep van malloc overeenkomt met een aanroep van free.
/* lifecycle
* 1. insert values (allocate)
* 2. search as needed (read-only)
* 3. free_tree(root) (deallocate)
* 4. root = NULL (avoid dangling)
*/Korte controle
Redeneer over veilig vrijgeven.
Samenvatting
Bij het zoeken in een BST wordt per stap vergeleken en in één deelboom afgedaald, met kosten die evenredig zijn met de hoogte. Het minimum is het meest linkse knooppunt en het maximum het meest rechtse.
Geef een boom vrij in navolgende volgorde, zodat de kinderen vóór de ouder worden vrijgegeven. Stel daarna de wortel in op NULL om een zwevende verwijzing te voorkomen.
Leer C met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 39
- Lessen
- 144
Veelgestelde vragen
Is de les “Zoeken en vrijgeven” gratis?
Ja — de volledige tekst van “Zoeken en vrijgeven” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus C Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus C Academy bevat in totaal 4 lessen.
Wat leer ik in “Zoeken en vrijgeven”?
Zoek knopen en geef geheugen vrij. Je oefent met C Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met C Academy te beginnen?
Ervaring vooraf is niet nodig. C Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Zoeken en vrijgeven”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over C Academy?
Ja. Elke les over C Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Boomknopen en -structuur
- Invoegen in een BST
- Doorlopen
- Zoeken en vrijgeven