Accueil › Coding & algorithmique › Les arbres binaires et leurs parcours
Les arbres binaires et leurs parcours
Récursivité, arbres et graphesavance
Un arbre binaire se parcourt naturellement par récursion : chaque sous-arbre est un arbre.
record Noeud(int valeur, Noeud gauche, Noeud droite) {}
// Préfixe : traiter le nœud AVANT les enfants
static void prefixe(Noeud n, List<Integer> r) {
if (n == null) return;
r.add(n.valeur());
prefixe(n.gauche(), r);
prefixe(n.droite(), r);
}
// Infixe : sur un ABR, donne les valeurs TRIÉES
static void infixe(Noeud n, List<Integer> r) {
if (n == null) return;
infixe(n.gauche(), r);
r.add(n.valeur());
infixe(n.droite(), r);
}
Seule la position de la ligne de traitement change : le squelette est identique.
Le parcours par niveau utilise une file, pas la récursion :
static List<List<Integer>> parNiveau(Noeud racine) {
List<List<Integer>> r = new ArrayList<>();
if (racine == null) return r;
Deque<Noeud> file = new ArrayDeque<>();
file.offer(racine);
while (!file.isEmpty()) {
int taille = file.size(); // ← délimite le niveau
List<Integer> niveau = new ArrayList<>();
for (int i = 0; i < taille; i++) {
Noeud n = file.poll();
niveau.add(n.valeur());
if (n.gauche() != null) file.offer(n.gauche());
if (n.droite() != null) file.offer(n.droite());
}
r.add(niveau);
}
return r;
}
Le piège majeur : valider un ABR en comparant seulement aux enfants directs. Il faut propager un intervalle.
Les termes à connaître
- Arbre binaire
Chaque nœud a au plus deux enfants, gauche et droit. La hauteur conditionne tout : O(log n) si l'arbre est équilibré, O(n) s'il dégénère en liste.
- Parcours en profondeur
Trois ordres selon la position du traitement du nœud : préfixe (nœud, gauche, droite), infixe (gauche, nœud, droite), suffixe (gauche, droite, nœud).
- Parcours infixe
Sur un arbre binaire de recherche, il produit les valeurs dans l'ordre croissant. C'est la propriété la plus exploitée en entretien.
- Arbre binaire de recherche (ABR)
Pour chaque nœud, tout le sous-arbre gauche est inférieur et tout le sous-arbre droit est supérieur. Recherche en O(h), où h est la hauteur.
- Parcours par niveau
Le BFS appliqué à un arbre : une file, et
file.size()au début de chaque tour pour délimiter le niveau.- Arbre équilibré
Un arbre dont les hauteurs des deux sous-arbres diffèrent d'au plus un, en tout nœud. C'est ce qui garantit le O(log n).
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.