Arbres binaires/Implémentation

Début de la boite de navigation du chapitre
Implémentation
Icône de la faculté
Chapitre no 2
Leçon : Arbres binaires
Chap. préc. :Définitions et propriétés
Chap. suiv. :Sommaire
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Arbres binaires : Implémentation
Arbres binaires/Implémentation
 », n'a pu être restituée correctement ci-dessus.

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 binairesModifier

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 arbresModifier

Calcul de la profondeurModifier

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

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