pfaExos2 - Alexandros Singh's Academic Homepage

Exercice 0 - Arbres binaires

Problème 0 : Implémentez les arbres binaires comme un type algébrique appelé binary_tree.
Problème 1 : Décrivez les valeurs de binary_tree correspondant aux arbres suivants.
Problème 2 : Implémentez une fonction count_nodes : binary_tree -> int qui compte le nombre de noeuds dans un arbre donné.
Problème 3 : Pouvez-vous penser à une version plus efficace ?
Problème 4 : Reformulez binary_tree en un nouveau type de données algébrique appelé decorated_binary_tree, paramétré par une variable de type 'a, de telle sorte que chaque noeud et chaque feuille stocke une valeur de type 'a.
Problème 5 : Décrivez les valeurs de decorated_binary_tree correspondant aux arbres suivants:
Problème 6 : Implémentez une fonction tree_sum : int decorated_binary_tree -> int qui additionne les valeurs stockées dans les noeuds et les feuilles d'un arbre en entrée.
Problème 7 : Pouvez-vous penser à une version plus efficace ?
Problème 8 : Implémentez une fonction search_tree : 'a decorated_binary_tree -> 'a -> bool qui recherche dans l'arbre d'entrée un élément correspondant à son second argument et renvoie true s'il en trouve un, sinon false.
Problème 9 : Pouvez-vous imaginer une version plus efficace ?

Dans ce qui suit, le type internally_decorated_tree est donné par :

type 'a internally_decorated_tree = 
    Leaf
    | Node of 'a * 'a internally_decorated_tree * 'a
    internally_decorated_tree

Exercice 1 - Map sur les arbres

Utilisez la fonction map sur les arbres dans vos solutions à tous les problèmes suivants.

Problème 0: Implémentez une fonction succ : int internally_decorated_tree -> int internally_decorated_tree telle que la valeur d'un noeud de succ t soit le successeur de la valeur du noeud correspondant de t.

Exercice 1: Fold sur les arbres

Utilisez la fonction fold sur les arbres dans vos solutions à tous les problèmes suivants.

Problème 0: Implémentez une fonction tree_sum : int internally_decorated_tree -> int telle que tree_sum t soit égale à la somme des valeurs de tous les noeuds de t.
Problème 1: Implémentez une fonction tree_prod : int internally_decorated_tree -> int telle que tree_prod t soit égal au produit des valeurs de tous les noeuds de t.
Problème 2: Implémentez une fonction search_in_tree : int internally_decorated_tree -> int -> bool telle que search_in_tree t e est vrai si e apparaît comme la valeur de n'importe quel noeud de t.

Devoir à rendre avant le 20 octobre 2023, 23h59, heure de Paris:

Problème 0 : La sérialisation d'un arbre est une liste qui contient tous les éléments de l'arbre dans un ordre donné. Un algorithme récursif pour sérialiser un arbre binaire (non vide) est le suivant :
- Soit \(v\) la valeur de la racine actuelle, \(l\) le sous-arbre de gauche, et \(r\) le sous-arbre de droite. Soit \(s_v = [v]\) une liste dont le seul élément est la valeur \(v\) de la racine courante, \(s_l\) la sérialisation du sous-arbre gauche \(l\), et \(s_r\) la sérialisation du sous-arbre droit \(r\). Les valeurs \(s_l\) et \(s_r\) sont calculées récursivement.
- L'algorithme renvoie ensuite la sérialisation de l'arbre entier en concaténant les \(s_v, s_l,s_r\) dans l'un des trois ordres suivants :
  1. D'abord \(s_v\), puis \(s_l\), puis \(s_r\) (ordre préfixe).
  2. D'abord \(s_l\), puis \(s_r\), puis \(s_v\) (ordre postfixe).
  3. D'abord \(s_l\), puis \(s_v\), puis \(s_r\) (ordre infixe).
Implémenter trois fonctions serialise_prefix, serialise_postfix et serialise_infix en OCaml (en utilisant la fonction fold pour les arbres que nous avons écrite en classe), toutes de type 'a internally_decorated_tree -> 'a list qui exécutent les trois variantes (préfixe, postfixe et infixe) de l'algorithme ci-dessus sur les valeurs du type 'a internally_decorated_tree défini plus haut. Exemples de deux arbres (un int internally_decorated_tree et un string internally_decoracted_tree) et les résultats des trois fonctions mentionnées ci-dessus appliquées à chacun d'eux :

# (* définissant les exemples *);;
# let first_example = Node ("a",
                        Node ("b", Leaf,
                            Node ("c", Leaf, Leaf)),
                        Node ("d",
                            Node ("e", Leaf, Leaf), Leaf));;
val first_example : string internally_decorated_tree =
  Node ("a",
   Node ("b", Leaf,
    Node ("c", Leaf, Leaf)),
   Node ("d",
    Node ("e", Leaf, Leaf),
    Leaf))
# let second_example = Node ("0",
                        Node ("1",
                            Node ("2", Leaf, Leaf),
                            Node ("3", Leaf,
                                Node ("4", Leaf, Leaf))),
                        Node ("5",
                            Node ("6", Leaf, Leaf), Leaf));;
val second_example : string internally_decorated_tree =
  Node ("0",
   Node ("1",
    Node ("2", Leaf, Leaf),
    Node ("3", Leaf,
     Node ("4", Leaf, Leaf))),
   Node ("5",
    Node ("6", Leaf, Leaf),
    Leaf))
# (* appliquant nos fonctions aux deux exemples *);;
# serialise_prefix first_example;;
- : string list = ["a"; "b"; "c"; "d"; "e"]
# serialise_prefix second_example;;
- : string list = ["0"; "1"; "2"; "3"; "4"; "5"; "6"] 
# serialise_infix first_example;;
- : string list = ["b"; "c"; "a"; "e"; "d"]
# serialise_infix second_example;;
- : string list = ["2"; "1"; "3"; "4"; "0"; "6"; "5"]
# serialise_postfix first_example;;
- : string list = ["c"; "b"; "e"; "d"; "a"]
# serialise_postfix second_example;;
- : string list = ["2"; "4"; "3"; "1"; "6"; "5"; "0"]

Problème 1: La hauteur d'un arbre binaire est la longueur des chemins les plus longs (mesurés en nombre de nœuds parcourus) entre la racine et n'importe laquelle des feuilles. Voici un exemple d'arbre binaire de hauteur 4 avec un chemin maximal surligné.

Ecrivez une fonction tree_height : 'a internally_decorated_tree -> int qui calcule la hauteur d'un arbre donné en utilisant la fonction fold pour les arbres que nous avons écrite en classe pour implémenter l'algorithme récursif suivant :

Calculez récursivement la hauteur \(h_l\) du sous-arbre gauche et la hauteur \(h_r\) du sous-arbre droit.
La hauteur de l'arbre entier est alors \(1 + max(h_l, h_r)\).

Exemples de résultats attendus (en réutilisant les exemples du problème précédent) :

# tree_height first_example;;
- : int = 3
# tree_height second_example;;
- : int = 4