Problème : Forêt d'arbres de recherche binaire

On considère une forêt représentée sous forme d'une liste linéaire chaînée o� chaque maillon pointe un arbre de recherche binaire de mots de longueur L donnée. La liste est ordonnée selon la longueur des mots.

Exemple : Après l'insertion des données suivantes dans cet ordre : d, xde, mir, b, m, dfgy, xxyz, h, miz, dfaa, def, mirt, ghte, on obtient la forêt suivante :

Ecrire un algorithme qui recherche un mot de longueur L donnée dans la forêt et qui l'insère s'il ne le trouve pas.

On veut réaliser l'opération suivante :

" Lister tous les mots commençant par un caractère C donné " sans toutefois parcourir tous les noeuds des arbres de la forêt.

Ecrire le module (a) non récursif qui recherche le plus petit mot qui commence par un caractère C donné dans un arbre de racine A donné.

Afin de déterminer les suivants, par ordre alphabétique, du plus petit mot commençant par C, on utilise une pile.

- Que faut-il mettre dans cette pile ?

- Que faut-il alors rajouter dans le module de recherche ? Soit (a') ce nouveau module.

Utiliser (a') pour écrire un module (b) qui détermine les suivants du plus petit mot qui commencent par C.

Enfin, paramétrer et utiliser (a') et (b) pour écrire le module qui liste donc tous les mots de la forêt commençant par un caractère C donné.

N.B On utilisera les deux fonctions suivantes :

Prem(Mot) : donne le premier caractère du mot Mot.

Compare(Mot1, Mot2) : égal à 0 si Mot1 = Mot2,

: +1 si Mot1 > Mot2 et

: -1 autrement.

Exemple :

Si Mot1 = 'gh' et Mot2 = 'abc' alors Prem(Mot1) = 'g' et Compare(Mot1, Mot2) = +1.