Vue d'ensemble
Une liste est une structure linéaire : chaque élément a un seul successeur. Un arbre binaire est une structure ramifiée : chaque nœud peut avoir jusqu'à deux enfants, un à gauche et un à droite. C'est l'une des structures les plus fondamentales de l'informatique (tas, arbres de recherche, arbres syntaxiques, arbres de décision…). En OCaml, on l'exprime par un type somme récursif, et on écrit toutes les fonctions dessus par filtrage, exactement comme sur les listes.
- Définir un type somme récursif pour les arbres binaires.
- Construire un arbre « à la main » à partir des constructeurs.
- Écrire des fonctions récursives par filtrage sur les deux cas
VideetNoeud(g, x, d). - Calculer la taille (nombre de nœuds) et la hauteur d'un arbre.
- Réaliser un parcours infixe renvoyant la liste des étiquettes.
Prérequis
- Le filtrage (
match … with) et la récursivité sur les listes OCaml (fiche ocaml-filtrage-listes). - Les constructeurs d'un type somme (les
|qui séparent les cas), et le fait qu'un type peut se référer à lui-même. - La concaténation de listes avec l'opérateur
@et la notation[x]pour une liste à un élément.
Les arbres, c'est le moment où la récursivité devient concrète. Si le passage « un cas du type = un cas du match » ne clique pas encore, un point de 30 min avec un de nos mentors alumni X · Centrale · Mines suffit souvent à tout débloquer.
Le type arbre binaire
Un arbre binaire d'entiers, c'est soit rien (l'arbre vide), soit un nœud qui porte une étiquette entière et possède deux sous-arbres. Cette phrase se traduit mot pour mot en OCaml.
On définit le type des arbres binaires d'entiers par :
type arbre =
| Vide
| Noeud of arbre * int * arbretype arbre =on déclare un nouveau type nommé arbre. Ce qui suit énumère toutes les formes possibles d'une valeur de ce type.| Videpremier cas : le constructeur Vide, sans argument. Il représente l'arbre vide (aucun nœud). C'est le cas de base de la structure.| Noeud of arbre * int * arbresecond cas : le constructeur Noeud prend un triplet (sous-arbre gauche, étiquette entière, sous-arbre droit). Le * forme le type produit du triplet, ce n'est pas une multiplication. Comme arbre apparaît dans sa propre définition, le type est récursif.NULL comme en C : Vide joue le rôle du sous-arbre absent, et le compilateur garantit qu'on traite toujours les deux cas.
Construire un arbre à la main
Construisons l'arbre suivant (on écrit l'étiquette dans chaque nœud) :
(* 1
/ \
2 3
/ \
4 5 *)
let a =
Noeud (
Noeud (Noeud (Vide, 4, Vide), 2, Vide),
1,
Noeud (Vide, 3, Noeud (Vide, 5, Vide)))let a =on nomme a l'arbre qu'on construit. Sa valeur est le grand Noeud qui suit.Noeud ( … , 1, … )le nœud racine porte l'étiquette 1. Son premier argument est le sous-arbre gauche, le troisième le sous-arbre droit.Noeud (Noeud (Vide, 4, Vide), 2, Vide)sous-arbre gauche : un nœud 2 dont l'enfant gauche est la feuille 4 (Noeud (Vide, 4, Vide) : deux sous-arbres vides) et dont l'enfant droit est Vide.Noeud (Vide, 3, Noeud (Vide, 5, Vide))sous-arbre droit : un nœud 3 sans enfant gauche (Vide) et dont l'enfant droit est la feuille 5.Vide : Noeud (Vide, v, Vide). Dans a, les feuilles sont les nœuds 4 et 5.
La taille : compter les nœuds
La taille d'un arbre est son nombre de nœuds. Le raisonnement est récursif et suit exactement les deux cas du type : un arbre Vide a 0 nœud ; un Noeud compte pour 1, plus les nœuds de ses deux sous-arbres.
La taille d'un arbre est définie par : et .
let rec taille a =
match a with
| Vide -> 0
| Noeud (g, _, d) -> 1 + taille g + taille dlet rec taille a =rec autorise la fonction à s'appeler elle-même : indispensable puisqu'on va rappeler taille sur les sous-arbres.match a withon filtre l'arbre a selon sa forme. Il n'y a que deux constructeurs, donc deux cas : le filtrage sera exhaustif.| Vide -> 0cas de base : un arbre vide contient zéro nœud. Sans ce cas, la récursion ne s'arrêterait jamais.| Noeud (g, _, d) -> 1 + taille g + taille dle _ ignore l'étiquette (on ne compte pas les valeurs, seulement les nœuds). On compte 1 pour le nœud courant, puis on ajoute la taille du sous-arbre gauche g et celle du droit d.Déroulons taille a sur l'arbre construit plus haut. On note chaque appel et sa valeur de retour :
| Appel | Cas filtré | Se réduit à | Valeur renvoyée |
|---|---|---|---|
taille (feuille 4) | Noeud | 1 + taille Vide + taille Vide | 1 |
taille (nœud 2) | Noeud | 1 + taille(feuille 4) + taille Vide | 1 + 1 + 0 = 2 |
taille (feuille 5) | Noeud | 1 + taille Vide + taille Vide | 1 |
taille (nœud 3) | Noeud | 1 + taille Vide + taille(feuille 5) | 1 + 0 + 1 = 2 |
taille (racine 1) | Noeud | 1 + taille(nœud 2) + taille(nœud 3) | 1 + 2 + 2 = 5 ✓ |
La fonction a donc renvoyé 5, ce qui correspond bien aux 5 nœuds 1, 2, 3, 4, 5.
La hauteur : la profondeur maximale
La hauteur mesure la longueur de la plus longue branche. Le schéma récursif est le même que pour la taille, mais au lieu d'additionner les deux sous-arbres, on prend le maximum (une seule branche compte, la plus profonde), et on ajoute 1 pour le niveau du nœud courant.
et . Avec cette convention, une feuille a pour hauteur , et un arbre vide a pour hauteur .
let rec hauteur a =
match a with
| Vide -> 0
| Noeud (g, _, d) -> 1 + max (hauteur g) (hauteur d)| Vide -> 0convention retenue : l'arbre vide a hauteur 0. Cas de base qui stoppe la récursion.1 + max (hauteur g) (hauteur d)max est la fonction prédéfinie qui renvoie le plus grand de ses deux arguments. Les parenthèses autour de (hauteur g) et (hauteur d) sont obligatoires : sans elles, OCaml lirait max hauteur g … comme si max prenait hauteur puis g comme arguments. On prend la plus profonde des deux branches, puis + 1 ajoute le niveau du nœud courant.| Appel | Se réduit à | Valeur renvoyée |
|---|---|---|
hauteur (feuille 4) | 1 + max 0 0 | 1 |
hauteur (nœud 2) | 1 + max (hauteur feuille 4) 0 | 1 + max 1 0 = 2 |
hauteur (feuille 5) | 1 + max 0 0 | 1 |
hauteur (nœud 3) | 1 + max 0 (hauteur feuille 5) | 1 + max 0 1 = 2 |
hauteur (racine 1) | 1 + max (hauteur nœud 2) (hauteur nœud 3) | 1 + max 2 2 = 3 ✓ |
La hauteur vaut 3 : la plus longue branche va de la racine 1 jusqu'à la feuille 4 (ou 5), soit trois nœuds empilés.
hauteur Vide = -1 (pour qu'une feuille ait hauteur 0). Les deux conventions sont correctes, mais elles décalent tout d'une unité : dans un énoncé, lisez toujours la convention imposée (souvent rappelée par « on convient que… »). Dans cette fiche on garde hauteur Vide = 0, donc feuille = 1.
Vide. Si vous écrivez seulement le cas Noeud, deux ennuis : (1) le compilateur avertit « this pattern-matching is not exhaustive », et (2) sur un arbre non vide la récursion descend jusqu'aux Vide des feuilles et lève Match_failure à l'exécution. Le cas de base Vide est ce qui fait converger la récursion.
Confondre « prendre le max » (hauteur) et « additionner » (taille) est l'erreur n°1 aux DS. Nos mentors alumni X · Centrale · Mines vous entraînent à reconnaître, sur n'importe quelle fonction d'arbre, si le nœud combine ses sous-arbres par somme, par max, ou par concaténation.
Trouver un mentor →Le parcours infixe
Parcourir un arbre, c'est visiter tous ses nœuds dans un ordre précis. Le parcours infixe (ou en ordre) visite d'abord tout le sous-arbre gauche, puis la racine, puis tout le sous-arbre droit. On renvoie la liste des étiquettes dans cet ordre.
let rec parcours a =
match a with
| Vide -> []
| Noeud (g, x, d) -> parcours g @ [x] @ parcours d| Vide -> []un arbre vide ne contient aucune étiquette : on renvoie la liste vide []. Cas de base.parcours g @ [x] @ parcours don concatène (opérateur @) trois listes dans l'ordre gauche, racine, droite : la liste du sous-arbre gauche, puis [x] (la liste à un seul élément contenant l'étiquette courante), puis la liste du sous-arbre droit. C'est cet ordre qui définit « infixe ».a. En appliquant parcours g @ [x] @ parcours d de bas en haut : parcours(nœud 2) = [4] @ [2] @ [] = [4; 2], parcours(nœud 3) = [] @ [3] @ [5] = [3; 5], puis parcours a = [4; 2] @ [1] @ [3; 5] = [4; 2; 1; 3; 5].
[x] dans la concaténation, on obtient le parcours préfixe ([x] @ parcours g @ parcours d, racine d'abord) et le parcours suffixe ou postfixe (parcours g @ parcours d @ [x], racine en dernier). La structure récursive, elle, ne change pas.
- Ouvre un
match a withsur l'arbre : il y aura exactement deux cas. - Traite le cas
Videen premier : c'est la valeur « neutre » (0 pour compter,[]pour lister, l'arbre lui-même pour transformer). - Dans le cas
Noeud (g, x, d), appelle récursivement la fonction surget surd. - Combine les deux résultats et l'étiquette
xselon le but :+(taille),max(hauteur),@(parcours).
Récap final — Ce qu'il faut absolument retenir
Les arbres binaires sont un type somme récursif à deux cas, et toute fonction dessus se calque sur ces deux cas par filtrage. Maîtrise ces réflexes :
- Sais-tu écrire de mémoire
type arbre = Vide | Noeud of arbre * int * arbreet expliquer pourquoi il est récursif ? - Sais-tu construire un arbre concret à la main avec
NoeudetVide, et reconnaître une feuille (Noeud (Vide, v, Vide)) ? - Sais-tu que la taille d'un
Videest 0 et que le casNoeudvaut1 + taille g + taille d? - Sais-tu que la hauteur combine les sous-arbres par
max(pas par+), avechauteur Vide = 0et feuille = 1 ? - Sais-tu pourquoi
max (hauteur g) (hauteur d)a besoin de ses parenthèses ? - Sais-tu écrire le parcours infixe
parcours g @ [x] @ parcours det le distinguer du préfixe et du suffixe ? - Sais-tu qu'oublier le cas
Videprovoque un filtrage non exhaustif et unMatch_failureà l'exécution ? - Sais-tu vérifier une convention de hauteur imposée par un énoncé (0 ou -1 pour l'arbre vide) ?
Exercices corrigés
Écris une fonction nb_feuilles : arbre -> int qui renvoie le nombre de feuilles de l'arbre (nœuds dont les deux sous-arbres sont Vide). Rappel : un arbre vide n'a aucune feuille.
Voir la correction détaillée
Il faut distinguer trois situations, donc trois motifs de filtrage : l'arbre vide, le nœud-feuille, et le nœud interne.
let rec nb_feuilles a =
match a with
| Vide -> 0
| Noeud (Vide, _, Vide) -> 1
| Noeud (g, _, d) -> nb_feuilles g + nb_feuilles dPourquoi cet ordre. Le motif Noeud (Vide, _, Vide) (une feuille) doit venir avant le motif général Noeud (g, _, d) : OCaml essaie les cas de haut en bas et s'arrête au premier qui correspond. Un nœud interne ne compte pas pour lui-même, il additionne les feuilles de ses deux sous-arbres. Sur l'arbre a de la fiche, on obtient 2 (feuilles 4 et 5).
Écris somme : arbre -> int qui renvoie la somme de toutes les étiquettes. Puis donne la valeur de somme a sur l'arbre a de la fiche.
Voir la correction détaillée
Même squelette que taille, mais au lieu de compter 1 par nœud on ajoute l'étiquette x. On ne peut donc plus l'ignorer : on la nomme.
let rec somme a =
match a with
| Vide -> 0
| Noeud (g, x, d) -> x + somme g + somme dDécryptage du cas Noeud. x est l'étiquette du nœud courant ; somme g et somme d somment récursivement les sous-arbres. Le cas Vide -> 0 est l'élément neutre de l'addition.
Application. Les étiquettes de a sont 1, 2, 3, 4, 5, donc somme a = 1 + 2 + 3 + 4 + 5 = 15.
Écris miroir : arbre -> arbre qui renvoie l'arbre symétrique (gauche et droite échangés à tous les niveaux). Que vaut alors le parcours infixe de miroir a, comparé à celui de a qui est [4; 2; 1; 3; 5] ?
Voir la correction détaillée
Cette fonction ne renvoie pas un nombre ni une liste mais un arbre. Le cas de base Vide se transforme en lui-même. Pour un nœud, on reconstruit un Noeud en inversant l'ordre : le sous-arbre droit reconstruit prend la place gauche, et réciproquement.
let rec miroir a =
match a with
| Vide -> Vide
| Noeud (g, x, d) -> Noeud (miroir d, x, miroir g)Le point clé. Dans le cas Noeud, on appelle miroir sur d pour la nouvelle branche gauche et sur g pour la nouvelle branche droite : l'échange se propage récursivement à tout l'arbre. L'étiquette x reste en place.
Effet sur le parcours infixe. Le miroir renverse l'ordre gauche/droite à chaque nœud, donc le parcours infixe de miroir a est le parcours infixe de a lu à l'envers : [5; 3; 1; 2; 4]. C'est un résultat général : parcours (miroir a) est toujours la liste renversée de parcours a.