Arbres binaires/Implémentation
Ce chapitre développe l'implémentation des arbres binaires en langage Caml / OCaml. Pour plus de précision sur la programmation même dans ces langages, vous pouvez consulter la leçon Premiers pas en OCaml.
Définition des arbres binaires
[modifier | modifier le wikicode]Afin de laisser le plus de liberté, on définit un type arbre_binaire à deux paramètres, permettant de spécifier le type des feuilles et des nœuds.
type ('f, 'n) arbre_binaire =
| Feuille of 'f
| Nœud of ('f, 'n) arbre_binaire * 'n * ('f, 'n) arbre_binaire
Ainsi, le type (int, int) arbre_binaire correspond à un arbre dont les feuilles et les nœuds sont étiquetés par des entiers.
Les objets suivants sont des exemples d'arbre binaire :
let f = Feuille 42;;
let f_chaine = Feuille "toto";;
let a = Nœud(Feuille 42, "a", Feuille 23);;
Remarque : On aurait aussi pu définir un arbre binaire par le type suivant :
type 'n arbre_binaire_alt =
| Vide
| Nœud of 'n arbre_binaire_alt * 'n * 'n arbre_binaire_alt
Mais cette définition ne permet pas de séparer le type des nœuds de celui des feuilles.
Opérations sur les arbres
[modifier | modifier le wikicode]Calcul de la profondeur
[modifier | modifier le wikicode]À l'aide d'une fonction récursive, on définit rapidement la profondeur d'un arbre binaire :
let rec profondeur = function
| Feuille _ -> 0
| Nœud (g, _, d) -> 1 + max (profondeur g) (profondeur d);;
Autres fonctions de base
[modifier | modifier le wikicode]À titre d'exercice, vous pouvez définir les fonctions qui déterminent le nombre de nœuds et le nombre de feuilles dans un arbre binaire.
