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 longueur 1.
```
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-arbre a1 par un sous-arbre a2 dans un arbre a, si le sous-arbre a1 appartient à a. Si le sous-arbre a1 n'appartient pas à a, la fonction retourne l'arbre a.
```
val remplace : 'a narbr -> 'a narbr -> 'a narbr -> 'a narbr = <fun>
```