Un arbre est une structure de données hiérarchique composée d’éléments appelés nœuds.
Il permet d’organiser des informations selon une relation de parenté.
Un arbre possède un nœud particulier appelé racine.
Chaque nœud peut avoir des enfants.
Un nœud qui n’a pas d’enfant est appelé une feuille.
Un arbre modélise une organisation hiérarchique (arbre généalogique, organisation de dossiers, etc.).
La structure d’un arbre permet de représenter des relations de dépendance ou d’organisation.
2️⃣ Arbres binaires
Un arbre binaire est un arbre particulier dans lequel chaque nœud possède au maximum deux enfants.
Ces deux enfants sont appelés sous-arbre gauche et sous-arbre droit.
Un arbre binaire peut être vide.
Chaque nœud peut être vu comme la racine d’un sous-arbre.
Les feuilles sont les nœuds qui ne possèdent ni sous-arbre gauche ni sous-arbre droit.
Un arbre binaire est défini de manière récursive :
soit il est vide ;
soit il est constitué d’une racine, d’un sous-arbre gauche et d’un sous-arbre droit.
3️⃣ Exemple d’arbre binaire
Considérons l’arbre binaire suivant :
Racine : 8
Feuilles : 1, 6 et 14
Sous-arbre gauche de 8 : arbre de racine 3
Sous-arbre droit de 8 : arbre de racine 10
Taille : 6 nœuds
Hauteur : 2 (longueur maximale d’un chemin entre la racine et une feuille)
Dans cet exemple :
Le nœud 3 possède deux enfants : 1 (gauche) et 6 (droit).
Le nœud 10 possède uniquement un sous-arbre droit.
Chaque sous-arbre est lui-même un arbre binaire.
4️⃣ Arbres binaires de recherche (ABR)
Un arbre binaire de recherche est un arbre binaire particulier qui respecte une propriété d’ordre.
Pour chaque nœud, toutes les valeurs du sous-arbre gauche sont strictement inférieures à la valeur du nœud.
Toutes les valeurs du sous-arbre droit sont strictement supérieures à la valeur du nœud.
Cette propriété est vraie pour tous les nœuds de l’arbre.
L’arbre présenté ci-dessus est un arbre binaire de recherche :
3 < 8 et 10 > 8
1 < 3 < 8
6 > 3 et 6 < 8
14 > 10 > 8
5️⃣ Points essentiels à retenir
Un arbre est une structure hiérarchique composée de nœuds reliés entre eux.
Un arbre binaire possède au maximum deux enfants par nœud.
Les notions importantes sont : racine, nœud, feuille, sous-arbre gauche, sous-arbre droit.
La taille correspond au nombre total de nœuds.
La hauteur correspond à la longueur du plus long chemin entre la racine et une feuille.
Un arbre binaire de recherche respecte une propriété d’ordre sur les valeurs.
🔗 Dans cet exercice, on montre comment identifier des végétaux à partir de caractéristiques de leurs folia, avec un arbre de décision.
🔗 Cet exercice du sujet zéro 2023 illustre la notion d'
arbre binaire de recherche.