TP7: Les Arbres n-aires

Le fichier à remplir est ici.

  1. 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.
  2. 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>
    
  3. Définir une fonction compter comptant le nombre de feuilles d'un arbre.

    val compter : 'a narbr -> int = <fun>
    
  4. 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>
    
  5. 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>
    
  6. 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>
    
  7. 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>
    
  8. Définir une fonction remplace qui remplace une occurrence 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>