3.1- TP - Arbres

Ce TP a pour but d'étudier la représentation des arbres binaires en OCaml.

I. Généralités

On étudiera dans ce TP des arbres contenant des chaines de caractère, on string en OCaml.

Question 1

Définissez un type arbre permettant de représenter un arbre binaire stockant des chaines de caractères dans ses noeuds et feuilles.

Puis, avant de continuer, regardez la case réponse et utilisez le type donné (pour éviter les problèmes).

OCaml

Loading editor...

type arbre = 
    | F of string
    | N of arbre * string * arbre (*l'ordre exact pourrait être différent, mais pour ce TP on utilisera celui-là*)
;;

Question 2

On vous donne un arbre en OCaml. Dessinez l'arbre correspondant (sur une feuille / tablette / paint...).

OCaml

Loading editor...

let a: arbre = N (
        N (
            N (F "très", "ceci", F "secret"), 
            "à", 
            F "est"), 
        "bonjour", 
        N (F "un", "tous", F "message"));;

Question 3

Quelle est la taille de l'arbre a ? Et sa hauteur ?

Vérifier son dessin

La fonction afficher_arbre du site dessine un arbre. On lui donne une fonction qui "découpe" l'arbre en son étiquette et la liste de ses fils :

let decoupe (a: arbre) = match a with
    | F x -> Some (x, [])
    | N (fg, x, fd) -> Some (x, [fg; fd]);;

afficher_arbre decoupe a;;

Question 4

Complétez la fonction suivante.

OCaml

Loading editor...

let rec hauteur (a: arbre) = match a with 
    |F _ -> (*à compléter*)
    |N (fg, _, fd) ->
        let hg = hauteur fg in 
        let hd = hauteur fd in
        (*à compléter*)
;;

OCaml

Loading editor...

hauteur a

Question 5

En suivant le même modèle, écrivez une fonction taille: arbre -> int qui calcule la taille d'un arbre.

OCaml

Loading editor...

II. Arbre phylogénétique du vivant

L'arbre OCaml suivant contient un sous ensemble simplifié de l'arbre phylogénétique du vivant, extrait de Lifemap.

OCaml

Loading editor...

let arbre_vivant: arbre = 
N
   (N
     (N (F "Algues vertes", "Plantes vertes",
       N (F "Mousse", "Plantes terrestres",
        N (F "Chêne", "Plantes à grains", F "Blé"))),
     "Eucaryotes",
     N (F "Champignons", "Opisthocontes",
      N (F "Eponges", "Animaux",
       N (F "Méduses", "Eumétazoaires",
        N
         (N (F "Nématodes (vers rond)", "Protostomiens",
           N (F "Araignées", "Arthropodes",
            N (F "Crustacés", "Mandibulés", F "Insectes"))),
         "Bilatériens",
         N (F "Etoiles de mer", "Deutérostomiens",
          N
           (N (F "Raies", "Chondrichthyes (poissons cartilagineux)",
             F "Requins"),
           "Vertébrés",
           N (F "Poissons à arrêtes",
            "Eutéléostomes (vertébrés à squelette osseux)",
            N
             (N (F "Reptiles (sauf crocodiles et tortues)", "Sauropsides",
               N (F "T-rex", "Dinosaures", F "Oiseaux")),
             "Amniotes",
             N (F "Marsupiaux", "Mammifères",
              N
               (N
                 (N (F "Lapins", "Glires",
                   N (F "Castor", "Rongeur", F "Rat")),
                 "Euarchontoglires",
                 N (F "Lémuriens", "Primates",
                  N
                   (N (F "Macaques", "Singes de l'ancien monde",
                     N (F "Gorille", "Grands singes",
                      F "Toi, qui lis cet arbre (Humain)")),
                   "Singes", F "Capucins"))),
               "Placentaires",
               N
                (N (N (F "Chat", "Félins", F "Tigre"), "Carnivores",
                  N
                   (N (F "Renard", "Canidés",
                     N (F "Chien", "Canis", F "Loup")),
                   "Caniformes", N (F "Ours", "Ursidés", F "Panda roux"))),
                "Laurasiatheria",
                N (N (F "Dauphin", "Artiodactyles", F "Vache"), "",
                 F "Chauve-souris"))))))))))))),
   "Ancêtre commun universel",
   N (F "Escherichia coli", "Bactéries", F "Planctomycètes"));;

Question 6

Appelez vos fonction hauteur et taille sur ce nouvel arbre.

OCaml

Loading editor...

Question 7

Ecrivez une fonction recherche: arbre -> string -> bool qui cherche une chaine de caractères dans l'arbre, et renvoie true si elle est présente, false sinon.

OCaml

Loading editor...

Question 8

Ecrivez une fonction ppac: arbre -> string -> string -> arbre (pour plus proche ancêtre commun), qui prend en argument un arbre, et deux chaines de caractères qu'on suppose présentes dans l'arbre, et renvoie l'arbre dont la racine est l'ancêtre commun le plus proche entre les deux (c'est à dire le plus petit sous-arbre qui contient les deux espèces).

On ne cherchera pas à faire une fonction optimisée.

Un noeud est le plus proche ancêtre commun entre "a" et "b", si "a" est dans sont fils gauche et "b" dans son fils droit, ou vice-versa.
On peut utiliser la fonction recherche pour chercher "a" dans le fils droit.
Si "a" et "b" sont dans le même fils, c'est que l'ancêtre commun est aussi dans ce fils.

OCaml

Loading editor...

Question 9

Quel est l'ancêtre commun le plus proche du "Dauphin" et des "Champignons" ?

OCaml

Loading editor...

Question 10

Ecrivez une fonction distance: arbre -> string -> string -> int qui renvoie la distance entre deux espèces dans l'arbre (donc le nombre de noeuds intermédiaires). Testez votre fonction.

Utilisez une fonction auxiliaire :

Vous pouvez écrire une fonction profondeur: arbre -> string -> int qui renvoie la profondeur à laquelle se trouve une espèce dans l'arbre. Cette fonction sera proche de la fonction recherche.
Ensuite, vous utiliser la fonction ppac, et calculer la profondeur de chaque espèce dans le fils droit ou gauche. La somme des deux est la distance les séparant.

OCaml

Loading editor...

OCaml

Loading editor...

OCaml

Loading editor...

Question bonus

Lisez la documentation du module Printf et écrivez une fonction pour afficher un arbre de manière jolie.

Ou bien, continuez le TP de la dernière fois.

OCaml

Loading editor...

Entrez le code donné en cours pour accéder à la solution :

Code d'accès