Nœuds et structure d’un arbre
Modélisez un nœud avec des pointeurs.
Nœuds et structure d’un arbre est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 1 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.
Qu'est-ce qu'un arbre binaire ?
Un arbre binaire est une structure hiérarchique dans laquelle chaque nœud contient une valeur et des liens vers au plus deux enfants : un enfant gauche et un enfant droit.
Le nœud situé tout en haut est la racine. Les nœuds sans enfant sont des feuilles. Cette forme rend les arbres binaires très adaptés à la recherche rapide, au tri et au traitement récursif.
La structure Node
En C, nous représentons un nœud avec une structure qui stocke les données ainsi que deux pointeurs autoréférentiels.
Chaque pointeur désigne un autre Node, ou NULL lorsqu'il n'y a pas d'enfant de ce côté.
struct Node {
int value;
struct Node *left;
struct Node *right;
};Pourquoi des pointeurs autoréférentiels
Un nœud ne peut pas contenir un autre nœud complet par valeur, car cela nécessiterait un espace de stockage infini. Il contient donc des pointeurs vers ses enfants.
Les pointeurs ont une taille fixe ; la structure conserve ainsi une taille connue tout en pouvant enchaîner d'autres nœuds sur le tas.
struct Node {
int value;
struct Node *left; /* 8 bytes on 64-bit */
struct Node *right; /* 8 bytes on 64-bit */
};Un typedef pratique
Écrire struct Node partout est fastidieux. Un typedef permet d'écrire simplement Node.
Le nom de balise reste nécessaire à l'intérieur de la structure, car le type n'y est pas encore complètement défini.
typedef struct Node {
int value;
struct Node *left;
struct Node *right;
} Node;Allouer un Node
Les nœuds résident sur le tas et sont créés avec malloc. Nous définissons la valeur et initialisons les deux pointeurs d'enfant à NULL.
Vérifiez toujours que malloc n'a pas renvoyé NULL avant d'utiliser la mémoire.
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;
}Construire un petit arbre à la main
Pour comprendre les liens, relions manuellement trois nœuds : une racine avec deux enfants.
Ce programme construit l'arbre et affiche les valeurs ; normalement, nous le libérerions ensuite, comme nous le verrons plus tard.
#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;
}Atteindre les petits-enfants
Vous parcourez l'arbre en enchaînant l'opérateur flèche. root->left->right descend vers l'enfant gauche, puis vers son enfant droit.
Avant de suivre un pointeur, assurez-vous qu'il n'est pas égal à NULL, sinon votre programme plantera.
/* root
* \
* right (15)
* \
* right->right (20)
*/
if (root->right != NULL && root->right->right != NULL)
printf("%d\n", root->right->right->value);Compter les nœuds récursivement
La récursion convient naturellement aux arbres. Pour compter les nœuds, un sous-arbre vide en contient zéro ; sinon, comptez le nœud courant ainsi que les deux sous-arbres.
La vérification de NULL constitue le cas de base qui arrête la récursion.
int count_nodes(Node *root) {
if (root == NULL) return 0;
return 1 + count_nodes(root->left)
+ count_nodes(root->right);
}Mesurer la hauteur
La hauteur d'un arbre est le plus long chemin entre la racine et une feuille, mesuré en arêtes.
Nous prenons la plus grande des hauteurs des deux sous-arbres et ajoutons un. Un arbre vide reçoit la hauteur -1, afin qu'un nœud seul ait une hauteur de 0.
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);
}Identifier les feuilles
Une feuille est un nœud sans enfant : left et right valent tous deux NULL.
Ce petit assistant est utile dans de nombreuses routines de parcours et de comptage.
int is_leaf(Node *n) {
return n != NULL && n->left == NULL && n->right == NULL;
}Mettre la structure à contribution
Nous construisons ici un petit arbre et indiquons son nombre de nœuds et sa hauteur à l'aide des assistants récursifs.
Remarquez que ces assistants ne supposent jamais une forme fixe ; ils fonctionnent pour tout arbre, car la récursion suit les pointeurs réels.
#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;
}Vérification rapide
Vérifiez votre compréhension de la structure d'un nœud.
Récapitulatif
Un nœud d'arbre binaire contient une valeur et deux pointeurs autoréférentiels (left, right), définis à NULL lorsqu'ils sont absents.
Nous allouons les nœuds avec malloc, les relions manuellement et les traitons récursivement. La vérification de NULL est toujours le cas de base pour le comptage, la hauteur et les tests de feuilles.
Questions Fréquemment Posées
La leçon « Nœuds et structure d’un arbre » est-elle gratuite ?
Oui — le texte complet de « Nœuds et structure d’un arbre » 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 « Nœuds et structure d’un arbre » ?
Modélisez un nœud avec des pointeurs. 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 1 sur 4.
Combien de temps prend la leçon « Nœuds et structure d’un arbre » ?
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