Enoncé 12 : Arbres - Piles   Corrigé 12

Problème : Navigation dans un arbre de recherche binaire

1. Ecrire le module Recherche ( Arbre, A, P, Pile) qui recherche une donnée A dans un arbre de recherche binaire de racine Arbre. Ce module rend le pointeur P de l'élément A s'il existe, NIL sinon. Ce module rend également le chemin , dans la pile Pile, composé de tous les nœuds traversés avec pour chaque nœud le sens de sortie ( gauche ou droite)

2. Utiliser cette pile pour écrire la fonction Suivantinordre(P) qui rend le pointeur du prochain élément parcouru en inordre d'un élément de pointeur P donné s'il existe, NIL sinon. La pile doit être modifiée de telle sorte que l'on puisse déterminer le suivant du suivant, le suivant du suivant du suivant, etc.

3. Utiliser les modules Recherche et Suivantinordre pour lister toutes les valeurs comprises entre 2 valeurs A et B données. On suppose que A existe et que B > A.

4. Utiliser Suivantinordre pour lister toutes les feuilles de gauche à droite.

5. Utiliser la O-notation pour déterminer la complexité de la fonction Suivantinordre. Justifier.

* * * * *