Structure d'arbre binaire
Définition : Arbre binaire
Un arbre binaire est une structure arborescente où chaque position dans l'arbre donne sur exactement deux branches.
C'est un ensemble fini de noeuds défini par l'un des deux cas suivant :
Soit l'arbre est vide, et ne contient aucun noeud.
Soit l'arbre n'est pas vide, et contient des noeuds strcturés de la manière suivante :
l'un des noeuds est appelé racine de l'arbre ;
les autres noeuds sont répartis en deux sous-ensembles nommés sous-arbre gauche et sous-arbre droit et définis récursivement de la même manière ;
la racine est reliée par une branche aux deux sous-ensembles de l'arbre s'ils ne sont pas vides.
Exemple : Représentation
Pour représenter un arbre binaire non vide la majorité du temps, on place la racine en haut et les sous-arbres gauche et droits à gauche et à droite sous la racine, reliés par un trait. Les noeuds sont généralement par des cercles.
Simulation : Exercice
Dessiner tous les arbres binaires ayant respectivement 1, 2 et 3 noeuds.
Vocabulaire
Définition : Feuille
Une feuille est un arbre qui ne contient qu'un seul noeud (à ne pas confondre avec arbre binaire vide).
Définition : Taille
La taille d'un arbre est le nombre de noeuds de cet arbre.
Définition : Hauteur
La hauteur d'un arbre est le plus grand nombre de noeuds possible rencontrés entre une racine et une feuille en n'empruntant que des sous-arbres.
Par exemple, l'arbre binaire ci-contre est d'hauteur 3.
Une définition récursive est possible :
Un arbre vide a pour hauteur 0.
Un arbre non vide a pour hauteur le maximum de la hauteur des sous-arbres de la racine plus 1.
Remarque : Nombre de noeuds et hauteur
Soit n la taille d'un arbre binaire, et h la hauteur de ce même arbre binaire. Ces deux valeurs sont liées par l'inéquation :
\(h \le n \le 2^h-1\)
On peut prouver \(h \le n\) grâce aux arbres ayant que des sous-arbres gauches ou que des sous-arbres droits. Ces arbres sont appelés peignes.
On peut prouver \(n \le 2^h-1\) grâce aux arbres ayant le plus grand nombre de noeuds à une hauteur fixe. On dit que ces arbres sont parfaits.
Simulation : Exercice
Sachant qu'il y a :
1 arbre binaire de taille 0 ;
1 arbre binaire de taille 1 ;
2 arbres binaires de taille 2 ;
5 arbres binaires de taille 3 ;
14 arbres binaires de taille 4.
Combien y'a-t-il d'arbres binaires de taille 5 ?
Et où sont les données ?
C'est bien beau d'avoir des arbres, mais on les stocke où nos données ?
Et bien, dans les noeuds !
