Aller au contenu

Premières fonctions

On va considérer le type des arbres binaires 'a arbre_bin défini par :

type 'a arbre_bin = 
    | Nil 
    | Noeud of 'a arbre_bin * 'a * 'a arbre_bin

Question 1. Écrire des fonctions permettant de calculer la taille et la hauteur d'un arbre, ainsi qu'une fonction permettant de déterminer si un arbre est réduit à une feuille.

Tests 
assert (taille Nil = 0);
assert (taille (Noeud(Nil,3,Nil)) = 1);
assert (taille (Noeud(Nil,'a',Nil)) = 1);
assert (taille (Noeud(Nil,'a',Noeud(Nil,'b',Nil))) = 2);
"Valide";;

assert (hauteur Nil = -1);
assert (hauteur (Noeud(Nil,3,Nil)) = 0);
assert (hauteur (Noeud(Nil,'a',Nil)) = 0);
assert (hauteur (Noeud(Nil,'a',Noeud(Nil,'b',Nil))) = 1);
"Valide";;

assert (not (feuille Nil));
assert (feuille (Noeud(Nil,3,Nil)));
assert (feuille (Noeud(Nil,'a',Nil)));
assert (not (feuille (Noeud(Nil,'a',Noeud(Nil,'b',Nil)))));
"Valide";;
Corrigé 
let rec taille (a : 'a arbre_bin) : int = match a with
    | Nil -> 0
    | Noeud(g,x,d) -> 1 + taille g + taille d

let rec hauteur (a : 'a arbre_bin) : int = match a with
    | Nil -> -1
    | Noeud(g,x,d) ->
            1 + max (hauteur g) (hauteur d)

let feuille (a : 'a arbre_bin) : bool = match a with
    | Nil -> false
    | Noeud(g, x, d) -> g = Nil && d = Nil

Question 2. Dans cette question, on va identifier un nœud à son étiquette.

Déterminer des fonctions renvoyant, sous forme d'une liste d'étiquettes, les nœuds, les feuilles et les nœuds internes d'un arbre.

Allez regarder les tests si vous avez un doute sur ce qui doit être renvoyé.

Tests 
assert(noeuds Nil = []);
assert(noeuds (Noeud(Nil,1,Nil)) = [1]);
let a = Noeud(
    Noeud(Nil, 2, Noeud(Nil, 3, Nil)),
    4, Noeud(Noeud(Nil, 5, Nil), 6,
        Noeud(Nil, 7, Nil))) in
assert(List.sort Stdlib.compare (noeuds a)
    = [2;3;4;5;6;7]);
"Valide";;

assert(feuilles Nil = []);
assert(feuilles (Noeud(Nil,1,Nil)) = [1]);
let a = Noeud(
    Noeud(Nil, 2, Noeud(Nil, 3, Nil)),
    4, Noeud(Noeud(Nil, 5, Nil), 6,
        Noeud(Nil, 7, Nil))) in
assert(List.sort Stdlib.compare (feuilles a)
= [3;5;7]);
"Valide";;

assert(noeuds_internes Nil = []);
assert(noeuds_internes (Noeud(Nil,1,Nil)) = []);
let a = Noeud(
    Noeud(Nil, 2, Noeud(Nil, 3, Nil)),
    4, Noeud(Noeud(Nil, 5, Nil), 6,
        Noeud(Nil, 7, Nil))) in
assert(List.sort Stdlib.compare 
    (noeuds_internes a)
= [2;4;6]);
"Valide";;
Corrigé 
let rec noeuds (a : 'a arbre_bin) : 'a list = 
    match a with
    | Nil -> []
    | Noeud(g, x, d) ->
        x :: (noeuds g @ noeuds d)

let rec feuilles (a : 'a arbre_bin) : 'a list = 
    match a with
    | Nil -> []
    | Noeud(g, x, d) ->
        if feuille a then [x]
        else feuilles g @ feuilles d

let rec noeuds_internes (a : 'a arbre_bin) = 
    match a with
    | Nil -> []
    | Noeud(Nil, _, Nil) -> []
    | Noeud(g, x, d) ->
        x :: (noeuds_internes g @ noeuds_internes d)

Question 3. Écrire une fonction permettant de déterminer si un arbre binaire est strict.

Tests 
assert(not (est_strict Nil));
assert(est_strict (Noeud(Nil, 1, Nil)));
let a = Noeud(
    Noeud(Nil, 2, Noeud(Nil, 3, Nil)),
    4, Noeud(Noeud(Nil, 5, Nil), 6,
        Noeud(Nil, 7, Nil))) in
assert(not (est_strict a));
let b = Noeud(
    Noeud(Nil, 2, Nil),
    4, Noeud(Noeud(Nil, 5, Nil), 6,
        Noeud(Nil, 7, Nil))) in
assert(est_strict b);
"Valide";;
Corrigé 
let rec est_strict (a : 'a arbre_bin) : bool =
    match a with
    | Nil -> false
    | Noeud(Nil, x, Nil) -> true
    | Noeud(g, x, d) -> g <> Nil && d <> Nil && est_strict g && est_strict d

Question 4. Écrire une fonction qui renvoie les sous-arbres d'un arbre, en dupliquant les sous-arbres identiques.

Tests 
assert(sous_arbres Nil = [ Nil ]);
let a = Noeud(Nil, 1, Nil) in
assert(List.sort Stdlib.compare (sous_arbres a)
    = [ Nil; Nil; a ]);
let b = Noeud(Nil, 2, Nil) in
let c = Noeud(a, 3, b) in
assert(List.sort Stdlib.compare
    (sous_arbres c) =
    [Nil; Nil; Nil; Nil; a; b; c]);
"Valide";;
Corrigé 
let rec sous_arbres (a : 'a arbre_bin) : 'a arbre_bin list = 
    match a with
    | Nil -> [Nil]
    | Noeud(g, x, d) ->
       a :: (sous_arbres g @ sous_arbres d)

Pour accéder à un nœud de l'arbre, on descend en partant de la racine et en allant à gauche ou à droite. On peut donc représenter un tel chemin par une liste de déplacements :

type deplacement = Gauche | Droite
type chemin = deplacement list

Question 5. Écrire une fonction chemin_noeud : 'a arbre_bin -> chemin -> 'a option qui renvoie l'étiquette d'un nœud donné par son chemin. On utilise un type option en cas de chemin invalide.

Tests 
let a = Noeud(
    Noeud(Nil, 2, Noeud(Nil, 3, Nil)),
    4, Noeud(Noeud(Nil, 5, Nil), 6,
        Noeud(Nil, 7, Nil))) in
assert(chemin_noeud a [Gauche; Gauche] = None);
assert(chemin_noeud a [] = Some 4);
assert(chemin_noeud a [Droite; Gauche] = Some 5);
assert(chemin_noeud a [Droite; Droite] = Some 7);
assert(chemin_noeud a [Droite; Droite; Droite] = None);
"Valide";;
Corrigé 
let rec chemin_noeud (a : 'a arbre_bin) (l : chemin) : 'a option =
    match a, l with
    | Nil, _ -> None
    | Noeud(g,x,d), Gauche::q -> chemin_noeud g q
    | Noeud(g,x,d), Droite::q -> chemin_noeud d q
    | Noeud(g,x,d), [] -> Some x

Parcours

Sur le même modèle que les fonctions précédentes, on peut explorer un arbre en explorant à gauche puis à droite ses sous-arbres de manière récursive. Chaque nœud est donc vu trois fois :

  • une première fois quand on le découvre avant d'explorer son sous-arbre gauche
  • entre les deux explorations
  • enfin quand on a fini d'explorer son sous-arbre droit.

Question 6. Écrire des fonctions affiche_avant, affiche_milieu et affiche_apres qui parcourent et affichent les étiquettes d'un string arbre_bin selon les trois cas précédents. Note : il s'agit essentiellement du même code à une ligne près.

Tests 
let t = Noeud( Noeud(Nil, "1", Nil), "2", 
    Noeud(Nil, "3", Noeud(Nil, "4", Nil))) in
affiche_avant t (* doit afficher 2134 *);;

let t = Noeud( Noeud(Nil, "1", Nil), "2", 
    Noeud(Nil, "3", Noeud(Nil, "4", Nil))) in
affiche_milieu t (* doit afficher 1234 *);;

let t = Noeud( Noeud(Nil, "1", Nil), "2", 
    Noeud(Nil, "3", Noeud(Nil, "4", Nil))) in
affiche_apres t (* doit afficher 1432 *);;
Corrigé 
let rec affiche_avant a = match a with
    | Nil -> ()
    | Noeud(g,x,d) ->
        print_string x;
        affiche_avant g;
        affiche_avant d

let rec affiche_milieu a = match a with
    | Nil -> ()
    | Noeud(g,x,d) ->
        affiche_milieu g;
        print_string x;
        affiche_milieu d

let rec affiche_apres a = match a with
    | Nil -> ()
    | Noeud(g,x,d) ->
        affiche_apres g;
        affiche_apres d;
        print_string x

Première évaluation d'expression arithmétique

On va considérer des expressions comme \((2+3) \times 5\) représentées par des string arbre_bin ainsi :

let e = Noeud(
    Noeud( Noeud(Nil, "2", Nil), 
           "+", 
           Noeud(Nil, "3", Nil)), 
    "*", 
    Noeud(Nil, "5", Nil))

Question 7. Dessiner cet arbre. Évaluer les trois fonctions précédentes sur cet arbre. Qu'en déduire ?

Corrigé

La racine est étiquetée par "*", son fils gauche par "+" (avec les feuilles "2" et "3") et son fils droit est la feuille "5". On obtient :

  • affiche_avant e : *+235, c'est l'écriture préfixe de l'expression ;
  • affiche_milieu e : 2+3*5, c'est l'écriture infixe usuelle, mais les parenthèses ont disparu : on ne peut plus distinguer \((2+3)\times 5\) de \(2 + (3 \times 5)\) ;
  • affiche_apres e : 23+5*, c'est l'écriture postfixe, qu'on sait évaluer avec une pile (voir le TP sur les piles et files).

Les écritures préfixe et postfixe permettent de retrouver l'arbre, et donc l'expression, sans parenthèses ; ce n'est pas le cas de l'écriture infixe.

Question 8. Écrire une fonction d'évaluation qui calcule le résultat de cette expression.

On pourra utiliser int_of_string pour convertir une chaîne de caractères comme "42" en l'entier 42.

Tests 
let e = Noeud(Noeud( Noeud(Nil, "2", Nil), "+", Noeud(Nil, "3", Nil)), "*", Noeud(Nil, "5", Nil)) in
assert(evalue e = 25);
"Valide";;
Corrigé 
let rec evalue a = match a with
    | Nil -> failwith "Vide"
    | Noeud(Nil,x,Nil) -> int_of_string x
    | Noeud(g, x, d) ->
            let eg = evalue g in
            let ed = evalue d in
            match x with
            | "+" -> eg + ed
            | "*" -> eg * ed
            | _ -> failwith "Ope inconnue"

Arbres binaires stricts

Pour représenter des arbres dont les nœuds internes ont tous deux fils non vides, on va utiliser le type :

type ('a, 'b) arbre_strict = Feuille of 'a 
    | NoeudI of ('a, 'b) arbre_strict * 'b * ('a, 'b) arbre_strict

Ce type permet de représenter naturellement des expressions arithmétiques comme :

type operations = Plus | Mult

let e = NoeudI(
    NoeudI(Feuille 2, Plus, Feuille 3), 
    Mult, 
    Feuille 5)

Question 9. Écrire une fonction evalue : (int, operations) arbre_strict -> int qui évalue une telle expression.

Tests 
let e = NoeudI(NoeudI( Feuille 2, Plus, Feuille 3), Mult, Feuille 5) in
assert(evalue e = 25);
"Valide";;
Corrigé 
let rec evalue a = match a with
    | Feuille n -> n
    | NoeudI(g, x, d) ->
            let eg = evalue g in
            let ed = evalue d in
            match x with
            | Plus -> eg + ed
            | Mult -> eg * ed

Si on considère le type

type ('a, 'b) etiquette = F of 'a | N of 'b

on peut passer d'un ('a, 'b) arbre_strict à un ('a, 'b) etiquette arbre_bin et, dans certains cas, d'un ('a, 'b) etiquette arbre_bin à un ('a, 'b) arbre_strict.

Question 10. Écrire ainsi deux fonctions de conversion :

arbre_strict_vers_arbre_bin : ('a, 'b) arbre_strict -> ('a, 'b) etiquette arbre_bin
arbre_bin_vers_arbre_strict : ('a, 'b) etiquette arbre_bin -> ('a, 'b) arbre_strict option
Tests 
let asvab = arbre_strict_vers_arbre_bin in
assert(asvab (Feuille 1) = Noeud(Nil, F 1, Nil));
assert(asvab (NoeudI(Feuille 'a', 1, NoeudI(Feuille 'b', 2, Feuille 'c')))
    = Noeud(Noeud(Nil,F 'a',Nil), N 1, Noeud(Noeud(Nil,F 'b',Nil), N 2, Noeud(Nil, F 'c', Nil))));
"Valide";;

let abvas = arbre_bin_vers_arbre_strict in
assert(None = abvas Nil);
assert(None = abvas (Noeud(Nil, N 1, Nil)));
assert(None = abvas (Noeud(Nil, N 1, Noeud(Nil, F 2, Nil))));
assert(Some (Feuille 1) = abvas (Noeud(Nil, F 1, Nil)));
assert(Some (NoeudI(Feuille 'a', 1, NoeudI(Feuille 'b', 2, Feuille 'c')))
    = abvas (Noeud(Noeud(Nil,F 'a',Nil), N 1, Noeud(Noeud(Nil,F 'b',Nil), N 2, Noeud(Nil, F 'c', Nil)))));
"Valide";;
Corrigé 
let rec arbre_strict_vers_arbre_bin a =
    match a with
    | Feuille n -> Noeud(Nil, F n, Nil)
    | NoeudI(g, x, d) -> Noeud(arbre_strict_vers_arbre_bin g,
                            N x,
                            arbre_strict_vers_arbre_bin d)

let rec arbre_bin_vers_arbre_strict a =
    match a with
    | Noeud(Nil, F f, Nil) -> Some (Feuille f)
    | Noeud(g, N x, d) -> begin
            match arbre_bin_vers_arbre_strict g, arbre_bin_vers_arbre_strict d with
            | Some g', Some d' -> Some (NoeudI(g', x, d'))
            | _ -> None
        end
    | _ -> None

Dessin d'arbres

On va réaliser dans cette partie une fonction de dessin d'arbres avec la bibliothèque graphics. L'idée est de placer la racine et de dessiner les sous-arbres gauche et droit en dessous. Pour cela, il va falloir connaître la taille de ces sous-arbres en pixels.

On pourra consulter la documentation de graphics ici : Graphics

Question 11. Écrire une fonction pixels : 'a arbre_bin -> int * int qui renvoie un couple (largeur, racine) où largeur est la largeur en pixels d'un arbre dans son affichage et racine l'abscisse de la racine dans cet affichage.

Corrigé 
let rnoeud = 5 (* Le rayon du noeud *)
let marge = 2 (* la marge autour du noeud *)

let rec pixels a = match a with
    | Nil -> 0, 0
    | Noeud(g, _, d) -> 
            let lg, _ = pixels g in
            let ld, _ = pixels d in
            lg + ld + 2*(marge + rnoeud), lg + marge + rnoeud

Question 12. En déduire une fonction dessine : string arbre_bin -> int -> int -> unit telle que dessine a x y dessine l'arbre \(a\) en plaçant la racine en \((x, y)\).

On pourra utiliser draw_string pour dessiner l'étiquette, et text_size pour connaître les dimensions en pixels d'une chaîne.

Corrigé 
let rec dessine a x y =
    match a with
    | Nil -> ()
    | Noeud(g, e, d) ->
            (* On précalcule les tailles des sous-arbres *)
            let lg, rg = pixels g in
            let _, rd = pixels d in
            (* position de la racine gauche relativement à (x,y) *)
            let v_rg = x - lg - marge - rnoeud + rg in
            (* position de la racine droite relative (x, y) *)
            let v_rd = x + marge + rnoeud + rd in
            let dec_y = y - 2 * rnoeud - marge in

            moveto x y; lineto v_rg dec_y;
            moveto x y; lineto v_rd dec_y;
            fill_circle x y rnoeud;

            (* dimensions en pixels du texte de l'étiquette *)
            let tw, th = text_size e in
            moveto (x-tw/2) (y-th/2);
            set_color white;
            draw_string e;
            set_color black;

            dessine g v_rg dec_y;
            dessine d v_rd dec_y

Génération aléatoire d'arbres

Dans cette partie, ce qui nous intéresse est de générer aléatoirement des arbres pour en observer la structure. Les étiquettes ne sont pas pertinentes, on pourra donc au choix, soit considérer des unit arbre_bin, soit redéfinir un type d'arbres non étiquetés.

On va réaliser ici deux modèles de génération aléatoire d'arbres.

Premier modèle

Le premier modèle consiste, pour générer un arbre de \(n \ge 1\) nœuds, à choisir aléatoirement \(k\) dans \(\range{0}{n-1}\), à générer aléatoirement un arbre \(g\) à \(k\) nœuds et un arbre \(d\) à \(n-1-k\) nœuds puis à renvoyer l'arbre Noeud(g, (), d). Pour \(n = 0\), on renvoie l'arbre vide.

Question 13. Implémenter ce modèle avec une fonction genere_arbre_1 : int -> unit arbre_bin.

Tester votre fonction, notamment avec l'affichage de la partie précédente.

Corrigé

Random.int n renvoie un entier uniforme dans \(\range{0}{n-1}\).

let rec genere_arbre_1 n =
    if n = 0
    then Nil
    else begin
        let k = Random.int n in
        Noeud(genere_arbre_1 k, (), genere_arbre_1 (n - 1 - k))
    end

Second modèle

Pour le deuxième modèle, on va choisir un sous-arbre vide uniformément et le remplacer par un nœud.

Question 14. Écrire une fonction chemins_vides : 'a arbre_bin -> chemin list qui, étant donné un arbre, renvoie la liste des chemins permettant d'aboutir à un sous-arbre vide.

Corrigé 
let rec chemins_vides a =
    match a with
    | Nil -> [ [] ]
    | Noeud(g, _, d) ->
        List.map (fun c -> Gauche :: c) (chemins_vides g)
        @ List.map (fun c -> Droite :: c) (chemins_vides d)

Un arbre à \(n\) nœuds a exactement \(n+1\) sous-arbres vides : la liste renvoyée est de longueur \(n+1\).

Question 15. Écrire une fonction remplit : unit arbre_bin -> chemin -> unit arbre_bin qui remplace un sous-arbre vide, donné par son chemin, par un nœud.

Corrigé 
let rec remplit a c =
    match a, c with
    | Nil, [] -> Noeud(Nil, (), Nil)
    | Noeud(g, y, d), Gauche :: q -> Noeud(remplit g q, y, d)
    | Noeud(g, y, d), Droite :: q -> Noeud(g, y, remplit d q)
    | _ -> failwith "chemin invalide"

Question 16. En déduire une fonction genere_arbre_2 : int -> unit arbre_bin qui prend un entier n et construit un arbre à \(n\) nœuds en partant de l'arbre vide et en réalisant \(n\) remplacements d'un arbre vide par un nœud, le choix de l'arbre vide se faisant uniformément.

Note : on pourra utiliser List.nth et Random.int. Voir par exemple Random.

Corrigé 
let genere_arbre_2 n =
    let a = ref Nil in
    for _ = 1 to n do
        let vides = chemins_vides !a in
        let c = List.nth vides (Random.int (List.length vides)) in
        a := remplit !a c
    done;
    !a