TP6: Les Arbres Binaires

• Définir le type d'un arbre binaire polymorphe où la valeur au noeud est de même type que les valeurs aux feuilles.

• Définir deux fonctions créant respectivement un arbre à partir d'une valeur (une feuille), et un arbre à partir d'une valeur et de deux arbres (un nœud).

  val feuille : 'a -> 'a arbin = <fun>
  val noeud : 'a -> 'a arbin -> 'a arbin -> 'a arbin = <fun>
  

• Définir une comptant le nombre de feuilles d'un arbre binaire.

  val compter : 'a arbin -> int = <fun>
  

• Définir une fonction transformant un arbre en une liste. On pourra utiliser l'opérateur @ de concaténation de listes pour cette fonction. L'ordre de parcours de l'arbre doit être en profondeur d'abord (en premier les éléments du sous-arbre gauche, puis l'élément du nœud, puis les éléments du sous-arbre droit).

  val to_list : 'a arbin -> 'a list = <fun>
  

Soit une liste contenant des noms de produits. Il s'agit de construire à partir de cette liste un arbre binaire tel que à gauche d'un noeud (respectivement à droite) se trouvent des noms de produits tous inférieurs (respectivement tous supérieurs) à celui du noeud considéré. L'ordre sur les noms est celui de la fonction <, c'est à dire l'ordre du dictionnaire. Les feuilles de l'arbre contiennent la chaîne "Nil".

val constr : string list -> string arbin = <fun>

Exemple: à la liste définie ci-dessous correspond l'arbre suivant. (Ceci n'est qu'un exemple: votre solution peut avoir un produit différent à la racine.)

val l : string list =
  ["celeri"; "orge"; "mais"; "ble"; "tomate"; "soja"; "poisson"]

Le but de cet exercice est de calculer les abscisses et ordonnées de chaque noeud d'un arbre pour le dessiner sur une feuille de papier. Les coordonnées devront satisfaire les contraintes suivantes (voir la figure ci-dessous).

• Chaque noeud est verticalement à la distance d de son père. La racine est à la distance d du haut de la page.
• Le sous-arbre gauche d'un noeud r donné doit se trouver entièrement à gauche de la verticale située à une distance e à gauche de r, la règle symétrique est appliquée pour le sous-arbre droit de r.
• La feuille la plus à gauche doit se trouver à la distance e du bord gauche de la page.

type coord = int * int
type 'a arbinp = (coord * 'a) arbin
let d = 5
let e = 4

Le type 'a arbinp sert à représenter un arbre dont les nœuds et feuilles sont positionnés dans un repère cartésien. Écrire la fonction placer a qui prend un arbre a en entrée et qui rend l'arbre positionné dans le repère. On peut considérer que e et d sont des constantes connues de la fonction placer.

val placer : 'a arbin -> ((int * int) * 'a) arbin = <fun>

Exemple La mise en page de cet arbre

let t =
  noeud 'a'
    (feuille 'j')
    (noeud 'b'
       (noeud 'c'
          (noeud 'd' (feuille 'w') (feuille 'k'))
          (feuille 'z'))
       (feuille 'y'))

donne graphiquement le résultat suivant