Dans ce TP, nous définissons et manipulons des arbres binaires et écrivons des algorithmes simples pour les dessiner. La semaine prochaine, nous verrons un algorithme plus complexe pour obtenir des dessins de qualité pour les arbres binaires, nous réutiliserons donc le code de cette semaine.
Vous pouvez utiliser Core.Std pour les modules List et Option. On utilisera Gg et Vg pour dessiner les arbres, QCheck pour tester.
Recopiez ce type algébrique pour représenter les arbres binaires, paramêtré par le type de l'information associée à chaque nœud. On définit aussi un générateur aléatoire d'arbres binaires, de sorte à pouvoir utiliser QCheck pour tester les fonctions d'arbres. Il est paramétré par le type des nœuds, on fournit aussi deux générateurs pour des arbres avec des nœuds entiers ou des nœuds sans information.
Écrivez plusieurs fonctions, qui étant donné un entier $n$, construisent les arbres suivants. Tous les nœuds contiendront une valeur de type unit.
Écrivez la fonction calculant la hauteur d'un arbre binaire.
Testez que les arbres créés précédemment ont bien la hauteur souhaitée.
Écrivez une fonction calculant l'image miroir d'un arbre, comme illustré par le dessin ci-dessous.
 |  |
Testez que les chemins gauches et droits sont miroirs l'un de l'autre, que les chenilles gauches et droite sont miroirs l'un de l'autre, que l'arbre complet est miroir de lui-même.
Écrivez la fonction map des arbres binaires. map ~f construit une image de l'arbre en remplaçant chaque nœud par son image par la fonction f.
Écrivez une fonction fold des arbres binaires. Elle doit correspondre à faire un List.fold_left sur une liste des nœuds de l'arbre, en ordre infixe.
Écrivez une fonction retournant une liste de nœuds d'un arbre binaire, en ordre infixe. Pour cela, on utilisera une fonction annexe insert_nodes_of tree accu, ajoutant tous les nœuds de tree dans l'accumulateur accu.
Écrivez une fonction retournant la liste des paires (parent,enfant) d'un arbre binaire (observer l'arbre sur ces deux premiers niveaux).
Pour des raisons d'efficacité, il est préférable d'utiliser une fonction avec un argument supplémentaire qui contient la liste des arêtes au fur et à mesure qu'elle est construite.
Pour dessiner un arbre, il faut donner une position à chaque nœud. Nous allons donc écrire une fonction :
Le principe est simple : chaque sommet est dessiné avec un cercle de même rayon (disons $0.1$), chaque arête est dessinée par un segment entre les deux nœuds correspondant.
Voici un petit rappel de Vg, cela ne remplace pas la documentation mais vous permet de savoir de quelles fonctions vous avez besoin :
Commencez par écrire une fonction pour le dessin d'un sommet, et pour le dessin d'une arête.
Puis, utilisez les fonctions sur les arbres pour obtenir la liste des images de chaque nœud et de chaque arête. Utilisez Vg.I.blend pour aggréger toutes ces images en une seule image (Vg.I définit un monoïde, quel est le zéro et quel est l'opérateur binaire ?).
Vous obtenez alors :
Ajoutez le code pour l'export au format svg, en récupérant le module ExportSvg du premier TP. (L'image produite est centrée sur le point (0,5 ) et est un carré de longueur 20 , vous pouvez changer ces paramètres en modifiant la valeur view du module.)
Il nous faut maintenant convertir notre arbre portant des informations quelconques dans ses nœuds, en un arbre dont chaque nœud contient la position du nœud dans le dessin.
Attribuons la position $(0,0)$ à la racine. Donnez un algorithme qui dessine toutes les arêtes comme des diagonales de longueur 1 . Ainsi, si la position du père est $(x,y)$, la position de ses enfants est $(x-1,y-1)$ et $(x+1,y-1)$.
Testez votre fonction avec quelques arbres. Qu'en pensez-vous ?
Avec cet algorithme, la distance entre deux frères est toujours de $2$, ce qui provoque des chevauchements. Donnez un autre algorithme qui divise par deux la distance entre deux frères pour chaque profondeur, afin d'interdire les chevauchements. Plus des frères sont profonds, plus ils sont proches.
Ajoutez un troisième algorithme qui divise aussi la distance verticale entre deux profondeurs par deux à chaque niveau de l'arbre. Avec cet algorithme, tout arbre aura un dessin contenu dans un rectangle de dimension $4 \times 2$.
