430
A Rappels algorithmiques
A.5.3 Recherche
La fonction testant si un mot est présent ou non dans un trie de type Trie est
aussi décomposée en deux. D’abord la fonction d’appel « haut niveau » qui permet
également de traiter l’exception du trie vide.
Fonction chercher(Trie T, chaîne s)
// Précondition : T est une structure de type Trie, s est une chaîne de
caractères.
// Postcondition : renvoie Vrai si le trie contient la chaîne s et Faux sinon.
// Utilise : chercherNoeud
si T.racine == None alors
retourner Faux
sinon
retourner chercherNoeud(T.racine, s) // appel sur la racine
La fonction récursive pour une structure de type Noeud, où s’effectue réellement
le travail, s’écrit de la manière suivante.
Fonction chercherNoeud(Noeud N, chaîne s)
// Précondition : N est une structure de type Noeud.
// Postcondition : Retourne Vrai en cas de succès de la recherche de la
chaîne de caractères s dans le trie de racine N et Faux sinon.
// Variables locales : caractère c ;
// Utilise : estExterne, étendre, premièreLettre, finChaîne,
chercherNoeud
si estExterne(N) alors
retourner N.texte == s
c = premièreLettre(s)
si non(c dans N.enfant) alors
retourner Faux
sinon
retourner chercherNoeud(N.enfant[c], finChaîne(s))
A.5.4 Parcours d’un trie
Comme exemple de parcours, nous décrivons comment afficher la liste des mots
contenus dans l’arbre en ordre lexicographique (qui est le parcours préfixe de
la section A.1.2 étendu au cas non binaire). La procédure d’affichage pour une
structure de type Trie s’écrit