Arbres binaires/Implémentation

Début de la boite de navigation du chapitre

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.

fin de la boite de navigation du chapitre

Définition des arbres binaires

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

Calcul de la profondeur

À 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

À 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.