Arbres binaires
Un arbre binaire est une structure hiérarchique avec au plus deux enfants par nœud.
1
Définition et vocabulaire
Un arbre binaire organise des données en hiérarchie, avec au plus deux enfants par nœud.
- racine : nœud de départ.
- nœud : sommet de l’arbre.
2
Représentation
Graphique
- Branches visibles.
- Niveaux lisibles.
- Utilisé pour dessiner l’arbre.
En mémoire
- Chaque nœud stocke une valeur.
- Deux liens : gauche et droit.
nullmarque l’absence d’enfant.
Pense à un arbre généalogique : chaque personne peut avoir deux enfants au maximum.
3
Parcours classiques
| Parcours | Ordre |
|---|---|
| Préfixe | racine, gauche, droite |
| Infixe | gauche, racine, droite |
| Postfixe | gauche, droite, racine |
Mémo utile : PLD, LRD, LDR. Ne confonds pas préfixe et postfixe.
4
Récursivité et hauteur
La hauteur d’un arbre est liée à la plus longue descente vers une feuille, via ses sous-arbres.
- 1
Définir l’arbre par sa racine.
- 2
Traiter le sous-arbre gauche.
- L’arbre binaire repose sur la racine, les nœuds et les feuilles.
- Sa représentation relie chaque nœud à gauche et à droite.