TD/TP n°4 : Maple leaf rag ... recursions on
trees
Représentation des arbres binaires
Un arbre binaire sera représenté soit par une liste
vide, soit par une liste à 3 constituants : (noeud sag sad), où
"sag", acronyme de sous-arbre gauche, et "sad", acronyme de sous-arbre
droit, sont eux-mêmes des arbres et "noeud" est l'information d'un
type arbitraire stockée sur le noeud.
1. Définir une variable globale, arbre-vide, correspondant
à un arbre vide.
2. Définir une fonction qui permet de construire un arbre.
3. Définir des fonctions qui permettent de retourner les sous-arbres
gauche et droit et la valeur au noeud.
4. Définir une fonction qui teste si un arbre est vide.
5. Définir une fonction qui teste si un arbre est une feuille (sans
sous-arbre).
6. Définir une fonction qui permet de savoir si la liste passée
en argument correspond à une construction correcte d'un arbre.
7. Définir une fonction qui renvoie la hauteur de l'arbre.
8. Définir des fonctions qui effectuent des parcours préfixe,
infixe et postfixe d'un arbre. Ces fonctions doivent renvoyer une liste
contenant les noeuds du parcours correspondant.
9. Définir une fonction qui compte le nombre de feuilles d'un arbre.
10. Définir des fonctions qui renvoient le min (resp. le max)
des valeurs contenues dans un arbre de nombres.
Arbres de recherche
Un arbre de recherche est un arbre binaire dont les noeuds sont
des éléments d'un ensemble ordonné (on pourra prendre
l'ensemble des entiers naturels, sans perte de généralité)
et qui vérifie :
- chaque noeud est supérieur ou égal à toutes les
valeurs des noeuds de son sous-arbre gauche ;
- chaque noeud est inférieur ou égal à toutes les
valeurs des noeuds de son sous-arbre droit.
11. Définir une fonction qui permet d'insérer un élément
dans un arbre de recherche.
12. Construire un arbre de recherche à partir d'une liste non ordonnée
d'entiers passée en paramètre.
13. Définir une fonction qui permet de savoir si son argument est
un arbre de recherche.
14. Définir une fonction qui affiche par ordre croissant tous les
éléments contenus dans l'arbre de recherche.
15. Définir une fonction qui permet de savoir si un élément
appartient à un arbre de recherche. On utilisera les propriétés
des arbres de recherche pour répondre à cette question efficacement
(avec un nombre de tests inférieurs à la hauteur de l'arbre
+ 1).