Ouvrez le notebook interactif pour explorer les exemples et les parcours récursifs.
1. Pourquoi les arbres binaires ?
Dans la séance précédente, nous avons étudié les arbres généraux : une structure hiérarchique dont chaque nœud peut posséder un nombre quelconque d’enfants.
L’arbre binaire est un cas particulier très important : chaque nœud possède au plus deux sous-arbres : un sous-arbre gauche et un sous-arbre droit.
Cette légère contrainte simplifie fortement les algorithmes de parcours et fait de l’arbre binaire une structure fréquente en algorithmique.
2. Définition et vocabulaire
Un arbre binaire peut être défini de manière récursive :
Un arbre binaire est soit :
- vide ;
- soit un nœud contenant une valeur, relié à un sous-arbre gauche et un sous-arbre droit (qui sont eux-mêmes des arbres binaires).
On conserve le vocabulaire des arbres généraux : racine, nœuds, feuilles, hauteur, etc. La nouveauté porte uniquement sur la présence de deux sous-arbres ordonnés, c’est-à-dire que le sous-arbre gauche et le sous-arbre droit ne sont pas interchangeables.
3. Un premier aperçu des parcours
Grâce à leur structure régulière (gauche / droite), les arbres binaires se parcourent naturellement de trois façons classiques :
- préfixe : on visite la racine avant ses sous-arbres ;
- infixe : on visite la racine entre la visite des deux sous-arbres ;
- postfixe : on visite la racine après les deux sous-arbres.
Ces parcours seront détaillés pas à pas dans le notebook associé à travers de petites fonctions récursives.