Rechercher et libérer
Trouvez les nœuds et libérez la mémoire.
Rechercher et libérer est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.
Rechercher dans un BST
La recherche exploite la règle d’ordonnancement. À chaque nœud, nous comparons la cible à la valeur du nœud et nous nous dirigeons vers un seul sous-arbre.
Comme nous éliminons la moitié des nœuds restants à chaque étape, le coût de la recherche dépend de la hauteur de l’arbre, et non de sa taille.
Recherche récursive
La recherche récursive possède deux cas de base : un sous-arbre vide signifie que la valeur n’a pas été trouvée, tandis qu’une valeur correspondante signifie qu’elle a été trouvée.
Sinon, nous poursuivons récursivement à gauche ou à droite selon le résultat de la comparaison.
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);
}Recherche itérative
La recherche peut également prendre la forme d’une simple boucle, ce qui évite le surcoût de la récursion.
Nous suivons les pointeurs dans l’arbre jusqu’à trouver la cible ou atteindre la fin indiquée par NULL.
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 */
}La recherche en pratique
Ce programme construit un BST et recherche une valeur présente ainsi qu’une valeur absente, en affichant si chacune a été trouvée.
Un retour différent de NULL signifie que la valeur a été trouvée ; NULL signifie qu’elle ne se trouve pas dans l’arbre.
#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;
}Trouver le minimum
Dans un BST, la plus petite valeur se trouve dans le nœud le plus à gauche : continuez à suivre left jusqu’à ce qu’il vaille NULL.
De manière symétrique, le maximum se trouve dans le nœud le plus à droite. Ces fonctions auxiliaires sont utiles pour la suppression et les requêtes par intervalle.
Node *find_min(Node *root) {
if (root == NULL) return NULL;
while (root->left != NULL)
root = root->left;
return root;
}Pourquoi la libération est importante
Chaque nœud provient de malloc ; chaque nœud doit donc être rendu avec free. Oublier de libérer la mémoire provoque une fuite.
Mais vous ne pouvez pas libérer un nœud puis lire les pointeurs vers ses enfants : l’ordre de libération est donc essentiel.
Libérer en ordre postfixe
La manière sûre de libérer un arbre consiste à utiliser l’ordre postfixe : libérez d’abord les deux enfants, puis le nœud lui-même.
Ainsi, nous lisons les pointeurs left et right d’un nœud avant que la mémoire de ce nœud ne soit libérée.
void free_tree(Node *root) {
if (root == NULL) return;
free_tree(root->left);
free_tree(root->right);
free(root);
}Un ordre incorrect dangereux
Si vous libérez le nœud avant de parcourir récursivement ses enfants, vous provoquez un comportement indéfini : vous déréférenceriez une mémoire libérée pour atteindre les sous-arbres.
C’est un cas classique d’utilisation après libération. Libérez toujours les enfants en premier.
/* 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);
}Éviter les pointeurs pendants
Après le retour de free_tree, le pointeur racine d’origine contient toujours l’ancienne adresse, mais la mémoire n’existe plus.
Le remettre à NULL dans l’appelant empêche toute réutilisation accidentelle d’un pointeur pendant.
free_tree(root);
root = NULL; /* avoid a dangling pointer */Compter les nœuds libérés
Nous pouvons vérifier que la libération fonctionne en comptant les nœuds pendant le parcours postfixe, puis en libérant chacun d’eux.
Ce programme construit un arbre, le libère et indique combien de nœuds ont été libérés.
#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;
}Rechercher et libérer ensemble
Un cycle de vie complet : construire l’arbre, le rechercher, puis le libérer. Effectuer ces trois opérations garantit des programmes corrects et sans fuite mémoire.
Des outils comme Valgrind peuvent confirmer que chaque appel à malloc est associé à un appel à free.
/* lifecycle
* 1. insert values (allocate)
* 2. search as needed (read-only)
* 3. free_tree(root) (deallocate)
* 4. root = NULL (avoid dangling)
*/Vérification rapide
Réfléchissez à la désallocation sûre.
Récapitulatif
La recherche dans un BST compare la valeur et descend dans un seul sous-arbre à chaque étape ; son coût est proportionnel à la hauteur. Le minimum est le nœud le plus à gauche et le maximum, celui le plus à droite.
Libérez un arbre en ordre postfixe afin que les enfants soient libérés avant le parent, puis définissez la racine sur NULL pour éviter un pointeur pendant.
Questions Fréquemment Posées
La leçon « Rechercher et libérer » est-elle gratuite ?
Oui — le texte complet de « Rechercher et libérer » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Rechercher et libérer » ?
Trouvez les nœuds et libérez la mémoire. Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C Academy ?
Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Rechercher et libérer » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C Academy ?
Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Nœuds et structure d’un arbre
- Insérer dans un BST
- Parcours
- Rechercher et libérer