LISP -- Maîtrise d'Informatique
Exament 1995--1996
Un arbre binaire sur les entiers est représenté par:
- une liste () si l'arbre ne contient aucun élément;
- une liste de la forme (gauche élément droit), où
gauche
et droit sont des arbres binaires et élément un entier
supérieur
à tout élément de gauche et inférieur à
tout élément de droit,
si l'arbre contient au moins un élément.
Écrire en LISP les fonctions suivantes:
- créer à zéro arguments qui renvoie un arbre
vide,
- ajouter (à deux arguments: nom de l'arbre et
élément) qui renvoie l'arbre
constitué de l'arbre donné dans laquel on a ajouté
l'élément donné,
- arbredroit (à un argument: nom de l'arbre) qui renvoie l'arbre
droit de l'arbre
donné,
- arbregauche (à un argument: nom de l'arbre) qui renvoie
l'arbre gauche de l'arbre
donné,
- existe (à deux arguments: nom de l'arbre et élément)
qui renvoie true
si l'élément donné est dans l'arbre, et () sinon,
- lister (à un argument: nom de l'arbre) qui renvoie la liste
des éléments de
l'arbre donné (en ordre trié),
- supprimer (à deux arguments: nom de l'arbre et
élément) qui renvoie
l'arbre donné dans laquel on a supprimé l'élément
donné.
Écrire un programme de teste qui:
- crée un arbre A1 vide,
- ajoute 3 dans A1,
- ajoute 7 dans A1,
- ajoute 1 dans A1,
- ajoute 2 dans A1,
- ajoute 9 dans A1,
- teste si 7 est dans A1,
- teste si 10 est dans A1,
- liste A1,
- ajoute 0 dans A1,
- crée un arbre A2 égal à l'arbre gauche de A1,
- liste A1,
- liste A2,
- supprime 9 de A1,
- supprime 1 de A1,
- liste A1,
- liste A2.
Vincent Vajnovszki
sam 11 avr 12:38:30 DST 1998