Exercice 0 - Parcours en profondeur

-Problem 0: Implémenter en Racket trois fonctions prefix-traversal, infix-traversal, postfix-traversal qui prennent en argument un arbre et renvoient la liste des étiquettes des sommets dans l'ordre où ils sont visités selon les parcours en profondeur préfixe, infixe et postfixe, respectivement. Exemples de résultats attendus :

(define t1 '(1 (2 () ()) (3 () ())))
(define t2 '(1 (2 (4 () ()) (5 () ())) (3 () ())))
> (prefix-traversal t1)
'(1 2 3)
> (prefix-traversal t2)
'(1 2 4 5 3)
> (infix-traversal t1)
'(2 1 3)
> (infix-traversal t2)
'(4 2 5 1 3)
> (postfix-traversal t1)
'(2 3 1)
> (postfix-traversal t2)
'(4 5 2 3 1)

Exercice 1 - Parcours en largeur

-Problem 0: Implémenter en Racket une fonction breadth-first-traversal qui prend en argument un arbre et retourne la liste des étiquettes des sommets dans l'ordre où ils sont visités lors d'un parcours en largeur. Exemples de résultats attendus :

> (breadth-first-traversal t1)
'(1 2 3)
> (breadth-first-traversal t1)
'(1 2 3 4 5)

Exercice 3 - Opérations sur les arbres binaires de recherche

-Problem 1: Implémentez une fonction search qui prend en entrée un arbre (supposé être un ABR) et une valeur et qui retourne #t si la valeur apparaît comme l'étiquette d'un sommet de l'arbre, sinon elle retourne #f. Exemples de résultats attendus (en utilisant l'arbre ABR ci-dessus comme exemple) :

> (search example-abr 5)
#t
> (search example-abr 7)
#t
> (search example-abr 6)
#f
> (search example-abr 4)
#f

-Problem 1: Implémentez une fonction insert qui prend en entrée un arbre (supposé être un ABR) et une valeur et qui insère la valeur (c'est-à-dire qui insère un nouveau sommet dans l'arbre avec la valeur donnée comme étiquette) dans l'arbre tout en conservant la propriété d'être un ABR. Exemples de résultats attendus:

> (insert example-abr 6)
'(5 (2 (0 () ()) (3 () ())) (9 (7 (6 () ()) (8 () ())) (12 () ())))
> (insert example-abr 4)
'(5 (2 (0 () ()) (3 () (4 () ()))) (9 (7 () (8 () ())) (12 () ())))

-Problem 2: Implémenter une fonction remove qui prend en entrée un arbre (supposé être un ABR) et une valeur et si la valeur apparaît comme l'étiquette d'un sommet, elle effectue l'opération de suppression pour ce sommet dans l'arbre donné. Exemples de résultats attendus:

> (delete example-abr 8)
'(5 (2 (0 () ()) (3 () ())) (9 (7 () ()) (12 () ())))
> (delete example-abr 2)
'(5 (0 () (3 () ())) (9 (7 () (8 () ())) (12 () ())))
> (delete example-abr 5)
'(3 (2 (0 () ()) ()) (9 (7 () (8 () ())) (12 () ())))