Exercice 0 - Échauffement
-Problème 0 : Définir deux valeurs dans t1, t2 représentant les deux arbres suivants en Racket.
-Problème 1 : Essayez d'appliquer certaines des fonctions primitives telles que
tree?, leaf?, root, left-subtree, right-subtree sur ces deux valeurs.
Pouvez-vous deviner les résultats sans les regarder ?
Exercice 1 - Fonctions sur les arbres
-Problème 0 : Implementez une fonction num-leaves qui calcule le nombre de feuilles dans l'arbre représenté par son argment.
Exemples de résultats attendus :
> (num-leaves t1)
2
> (num-leaves t2)
3
find-max qui renvoie l'étiquette maximale. Implementez aussi une fonction find-min qui fait la même chose pour l'étiquette minimale.
Exemples de résultats attendus :
> (find-max t1)
3
> (find-max t2)
5
> (find-min t1)
1
> (find-min t2)
1
-Problème 2 : Ecrivez une fonction num_nodes qui calcule le nombre de noeuds dans l'arbre représenté par son argument. Exemple de résultats attendus :
> (num-nodes t1);;
1
> (num-nodes t2);;
2
-Problème 3 : Implémentez une fonction height qui calcule la hauteur (la plus grande
distance qu'une feuille peut avoir par rapport à la racine, mesurée en nombre
d'arêtes parcourues pour atteindre cette feuille à partir de la racine) d'un
arbre représenté par son argument.
Exemples de résultats attendus :
> (height t1);;
1
> (height t2);;
2
list-leaves qui renvoie une liste de
toutes les feuilles d'un arbre représenté par son argument. Exemples de
résultats attendus :
> (list-leaves t1);;
'(2 3)
> (list-leaves t2);;
'(4 5 3)
-Problème 5 : Implémenter une fonction replace-sum qui remplace les valeurs des noeuds internes par la somme des valeurs de leurs enfants (tout en laissant les feuilles intactes).
Exemples de résultats attendus :
> (replace-sum t1);;
'(5 (2 () ()) (3 () ()))
> (replace-sum t2);;
'(5 (9 (4 () ()) (5 () ())) (3 () ()))
-Problème 6 : Implémenter une fonction replace-depth qui remplace les valeurs des noeuds et des feuilles d'un arbre par leur distance à la racine.
Exemples de résultats attendus :
> (replace-depth t1);;
'(0 (1 () ()) (1 () ()))
> (replace-depth t2);;
'(0 (1 (2 () ()) (2 () ())) (1 () ()))
Devoirs à télécharger sur moodle
-Problème 0 : Ecrivez une fonction search qui prend comme arguments une représentation d'arbre
et une valeur et qui retourne #t si un sommet avec la valeur donnée comme label est trouvé, sinon elle retourne #f:
> (search t1 3)
#t
> (search t1 5)
#f
> (search t2 5)
#t
> (search t2 6)
#f