Leçons de niveau 15

Arbres binaires/Implémentation

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
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 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.