Structure de données - Arbre
Un arbre est une structure de données non linéaire typique, composée de nœuds et d'arêtes reliant les nœuds, utilisée pour représenter une relation hiérarchique « un-à-plusieurs » entre les éléments.
Terminologie de base des arbres
Profondeur 0
Profondeur 2
Pour comprendre les structures d'arbres, vous devez d'abord maîtriser quelques termes de base :
| Terme | Signification |
|---|---|
| Nœud racine (Racine) | Le nœud de départ d'un arbre, sans nœud parent |
| Nœud enfant (Enfant) | Le nœud au niveau suivant directement connecté à un nœud donné |
| Nœud parent (Parent) | Le nœud au niveau précédent directement connecté à un nœud donné |
| Nœud feuille (Feuille) | Un nœud sans enfants, c'est-à-dire la fin d'un arbre |
| Profondeur (Profondeur) | Nombre d'arêtes du nœud racine à ce nœud ; la racine a une profondeur de 0 |
| Hauteur (Hauteur) | Nombre d'arêtes de ce nœud au nœud feuille le plus profond |
Parcours d'arbre binaire
Préordre (racine → gauche → droite)
1 2 4 5 3Infixe (gauche → racine → droite)
4 2 5 1 3Postordre (gauche → droite → racine)
4 5 2 3 1Parcours par niveau (couche par couche)
1 2 3 4 5Les quatre méthodes de parcours courantes sont les suivantes :
| Méthode de parcours | Ordre de visite | Application typique |
|---|---|---|
| Parcours préordre | Racine → gauche → droite | Copie d'arbres, génération d'expressions préfixes |
| Parcours infixe | Gauche → racine → droite | L'ABR produit une séquence triée |
| Parcours postfixe | Gauche → droite → racine | Suppression d'arbres, génération d'expressions postfixées |
| Parcours par niveaux | Niveau par niveau, de gauche à droite | BFS, impression par niveaux |
Exemple
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
struct TreeNode* createNode(int value) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
/* Parcours préfixe : racine → gauche → droite */
void preOrder(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data); /* Visiter d'abord la racine */
preOrder(root->left); /* Puis parcourir le sous-arbre gauche */
preOrder(root->right); /* Enfin parcourir le sous-arbre droit */
}
/* Parcours infixe : gauche → racine → droite */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left); /* Parcourir d'abord le sous-arbre gauche */
printf("%d ", root->data); /* Puis visiter la racine */
inOrder(root->right); /* Enfin, parcourir le sous-arbre droit */
}
/* Parcours post-ordre : gauche → droite → racine */
void postOrder(struct TreeNode* root) {
if (root == NULL) return;
postOrder(root->left); /* Parcourir d'abord le sous-arbre gauche */
postOrder(root->right); /* Puis parcourir le sous-arbre droit */
printf("%d ", root->data); /* Enfin, visiter la racine */
}
int main() {
/* Construire l'arbre binaire suivant :
1
/ \
2 3
/ \
4 5 */
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Préfixe : "); preOrder(root); printf("\n"); /* 1 2 4 5 3 */
printf("Infixe : "); inOrder(root); printf("\n"); /* 4 2 5 1 3 */
printf("Postfixe : "); postOrder(root); printf("\n"); /* 4 5 2 3 1 */
return 0;
}
Arbre binaire de recherche (ABR)
Propriétés et opérations de l'ABR
Propriété : toutes les valeurs du sous-arbre gauche < racine < toutes les valeurs du sous-arbre droit
Insertion/recherche : aller dans le sous-arbre gauche si plus petit, aller dans le sous-arbre droit si plus grand, O(log n) lorsque équilibré
Le parcours infixe produit une séquence croissante : 20 30 40 50 60 70 80
Remarque : insérer dans l'ordre 1,2,3... dégénère en une liste chaînée O(n) ; un arbre AVL peut résoudre ce problème
Arbre binaire de recherche (BST)Exigence : Pour chaque nœud, toutes les valeurs du sous-arbre gauche sont inférieures à celle du nœud, et toutes les valeurs du sous-arbre droit sont supérieures à celle du nœud.
Exemple
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
/* Insertion dans un BST : localiser récursivement la position appropriée en fonction de la valeur
Complexité temporelle : O(h), h est la hauteur de l'arbre, O(log n) lorsqu'il est équilibré. */
struct TreeNode* insert(struct TreeNode* root, int value) {
if (root == NULL) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = value;
node->left = node->right = NULL;
return node;
}
if (value < root->data) {
root->left = insert(root->left, value); /* Si inférieur à la racine, insérer dans le sous-arbre gauche */
} else if (value > root->data) {
root->right = insert(root->right, value); /* Si supérieur à la racine, insérer dans le sous-arbre droit */
}
return root; /* Si égal, ignorer (un ABR ne stocke généralement pas de valeurs en double) */
}
/* Recherche dans l'ABR : comparer avec le nœud courant pour décider si l'on cherche à gauche ou à droite */
struct TreeNode* search(struct TreeNode* root, int target) {
if (root == NULL || root->data == target) {
return root; /* Cible trouvée ou nœud feuille atteint */
}
if (target < root->data) {
return search(root->left, target); /* La cible est plus petite, rechercher dans le sous-arbre gauche */
}
return search(root->right, target); /* La cible est plus grande, rechercher dans le sous-arbre droit */
}
/* Parcours infixe (vérifier l'ordre de l'ABR) */
void inOrder(struct TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
int main() {
struct TreeNode* root = NULL;
int values[] = {50, 30, 70, 20, 40, 60, 80};
/* Insérer séquentiellement pour construire l'ABR */
for (int i = 0; i < 7; i++) {
root = insert(root, values[i]);
}
printf("Parcours infixe de l'ABR (ordre croissant) : ");
inOrder(root); /* Sortie : 20 30 40 50 60 70 80 */
printf("\n");
/* Test de recherche */
int target = 40;
struct TreeNode* found = search(root, target);
printf("%d %s\n", target, found ? "Trouvé !" : "Non trouvé");
/* Sortie : 40 Trouvé ! */
return 0;
}
Autres extensionsDans le cas idéal (lorsque l'arbre reste équilibré), l'insertion, la suppression et la recherche dans un BST peuvent toutes atteindre O(log n). Cependant, si les données elles-mêmes sont ordonnées (par exemple en insérant 1, 2, 3, 4...), le BST dégénère en liste chaînée et l'efficacité tombe à O(n). Pour résoudre ce problème, l'informatique a développéArbre AVLet d'autres arbres binaires de recherche auto-équilibrés.