TP7: Les Arbres n-aires
Le fichier à remplir est ici. Conseil important Les structures de données manipulées dans ce TP sont mutuellement récursives (listes et arbres). Même s'il est possible de répondre aux questions avec une seule fonction récursive, il est fortement conseillé d'utiliser deux fonctions mutuellement récursives : une gérant la structure d'arbre et l'autre la structure de liste.
- Définir le type d'un arbre n-aire polymorphe où chaque noeud porte une valeur et une liste de nœuds représentant les sous-arbres. Dans la suite, on appelle feuille un nœud dont la liste des sous-arbres est vide. Ce type n'a qu'un seul constructeur.
Définir les quatre fonctions suivantes :
- une fonction créant une feuille à partir d'une valeur,
- une fonction créant un nœud à partir d'une valeur et d'une liste d'arbres,
- une fonction retournant la valeur associée à un arbre,
- une fonction retournant la liste des sous-arbres immédiats d'un arbre.
val feuille : 'a -> 'a narbr = <fun> val noeud : 'a -> 'a narbr list -> 'a narbr = <fun> val valeur : 'a narbr -> 'a = <fun> val sous_arbres : 'a narbr -> 'a narbr list = <fun>
Définir une fonction
compter
comptant le nombre de feuilles d'un arbre.val compter : 'a narbr -> int = <fun>
Définir une fonction
pluslongue
déterminant la longueur de la plus longue branche d'un arbre. Une feuille ou un nœud seul a pour longueur1
.val pluslongue : 'a narbr -> int = <fun>
Définir une fonction
listsa
retournant la liste des sous-arbres d'un arbre. Attention, il faut retourner tous les sous-arbres, même ceux en profondeur et même soi-même.val listsa : 'a narbr -> 'a narbr list = <fun>
Définir une fonction
listbr
retournant la liste des branches d'un arbre, une branche étant la liste des éléments de la racines à une feuille.val listbr : 'a narbr -> 'a list list = <fun>
Définir une fonction
egal
qui teste l'égalité de 2 arbres, en utilisant l'opérateur=
uniquement pour les valeurs.val egal : 'a narbr -> 'a narbr -> bool = <fun>
Définir une fonction
remplace
qui remplace une occurrence (et une seule) d'un sous-arbrea1
par un sous-arbrea2
dans un arbrea
, si le sous-arbrea1
appartient àa
. Si le sous-arbrea1
n'appartient pas àa
, la fonction retourne l'arbrea
.val remplace : 'a narbr -> 'a narbr -> 'a narbr -> 'a narbr = <fun>