A Rappels algorithmiques
431
Procédure afficher(Trie T)
// Précondition : T est une structure de type Trie.
// Postcondition : la liste des mots du trie T est affiché via des appels à une
fonction système print.
// Utilise : afficherNoeud
si T.racine == None alors
print("Le trie est vide!!!")
sinon
afficherNoeud(T.racine, "") // appel sur la racine
La procédure, pour la structure de type Noeud, est récursive et l’appel en un
nœud suppose que l’on connaît déjà le préfixe du chemin de la racine du trie au
nœud considéré. Ce préfixe est maintenu à jour au fur et à mesure du parcours.
Procédure afficherNoeud(Noeud N, chaîne préfixe)
// Précondition : N est un nœud d’un trie, préfixe correspond est une
chaîne contenant les lettres qui relient la racine du trie au nœud N.
// Postcondition : Si le nœud courant N est externe, la clé correspondante est
affichée via l’appel à une fonction système print.
// Variables locales : caractère c
// Utilise : afficherNoeud, estExterne, l’opérateur de concaténation ‘+’
pour les chaînes de caractères
si estExterne(N) alors
print(préfixe + N.text)
sinon
pour c dans N.enfant faire
afficherNoeud(N.enfant[c], préfixe + c)
Nous pouvons assez facilement adapter cet algorithme de parcours pour écrire
un algorithme réalisant des opérations ensemblistes sur deux ensembles de mots
représentés par des tries. Cela est laissé au lecteur.
A.5.5 Suppression
L’algorithme de suppression est le plus délicat à décrire. En effet, la suppression
d’un mot dans le trie peut amener à modifier la branche complète correspondante
du trie.
Nous écrivons l’algorithme de suppression pour la structure de type Trie.
431
Procédure afficher(Trie T)
// Précondition : T est une structure de type Trie.
// Postcondition : la liste des mots du trie T est affiché via des appels à une
fonction système print.
// Utilise : afficherNoeud
si T.racine == None alors
print("Le trie est vide!!!")
sinon
afficherNoeud(T.racine, "") // appel sur la racine
La procédure, pour la structure de type Noeud, est récursive et l’appel en un
nœud suppose que l’on connaît déjà le préfixe du chemin de la racine du trie au
nœud considéré. Ce préfixe est maintenu à jour au fur et à mesure du parcours.
Procédure afficherNoeud(Noeud N, chaîne préfixe)
// Précondition : N est un nœud d’un trie, préfixe correspond est une
chaîne contenant les lettres qui relient la racine du trie au nœud N.
// Postcondition : Si le nœud courant N est externe, la clé correspondante est
affichée via l’appel à une fonction système print.
// Variables locales : caractère c
// Utilise : afficherNoeud, estExterne, l’opérateur de concaténation ‘+’
pour les chaînes de caractères
si estExterne(N) alors
print(préfixe + N.text)
sinon
pour c dans N.enfant faire
afficherNoeud(N.enfant[c], préfixe + c)
Nous pouvons assez facilement adapter cet algorithme de parcours pour écrire
un algorithme réalisant des opérations ensemblistes sur deux ensembles de mots
représentés par des tries. Cela est laissé au lecteur.
A.5.5 Suppression
L’algorithme de suppression est le plus délicat à décrire. En effet, la suppression
d’un mot dans le trie peut amener à modifier la branche complète correspondante
du trie.
Nous écrivons l’algorithme de suppression pour la structure de type Trie.