Arbres ternaires

On veut lire un fichier et afficher tous les mots de ce fichier en ordre lexicographique. Dans le cours, on a déjà vu des méthodes qu'on pourrait utiliser :

1. On pourrait préallouer un grand tableau, le remplir avec des mots, et le trier en temps n log n en utilisant un des algorithmes du TP 4. Un des problèmes avec cette solution est qu'on ne connait pas le nombre de mots dans le fichier, donc ce n'est pas évident de savoir comment choisir la taille du tableau.
2. On pourrait stocker tous les mots dans une liste chaînée triée, ce qui résoud le problème de l'allocation d'un tableau de taille statique. Puis, on parcourt la liste une fois pour afficher les mots en ordre lexicographique. On a écrit un tel programme en TP 6. Vous pouvez essayer de lancer ce programme avec le fichier big.txt (6.5Mo). Le problème principal avec cette solution est que la complexité est trop importante (quadratic).

Dans ce TP, vous allez écrire une implémentation d'un arbre ternaire pour résoudre ce problème très efficacement (en temps linéaire, plus rapide qu'un tri standard).

Les définitions de type suivantes permettent de représenter un arbre ternaire :

Noter qu'on ne stocke pas le nombre d'occurrence d'un mot, donc on ne va pas gérer de doublons. On stocke chaque mot seulement une fois.

A part ces définitions, vous êtes libre de faire votre implémentation d'un arbre ternaire comme vous voulez. La seule contrainte est que l'exercice 4 doit être fait. Les trois premiers exercices sont conseillés mais facultatifs. Par exemple, vous n'avez pas besoin d'une fonction pour chercher un mot dans l'arbre pour finir l'exercice 4, mais ca peut être plus facile d'écrire une fonction pour l'insertion si on l'a fait.

Un arbre ternaire contenant les mots le, la, de, un et une est représenté comme dans la figure suivante :

1. Écrire une fonction pour allouer l'espace mémoire d'un noeud et l'initialiser avec un caractère.
2. Écrire une fonction main qui utilise cette fonction pour créer (à la main) l'arbre dans la figure ci-dessus.
3. Écrire une fonction pour chercher un mot dans un arbre ternaire et la tester avec l'arbre créé dans l'exercice précédent. Voici, le psuedo-code pour une solution récursive :

   rechercher(t, mot):
   si t est vide, alors le mot n'est pas dans l'arbre
   si le premier caractère du mot == le caractère dans la racine, alors
      si le premier caractère du mot == '\0', alors
         le mot est dans l'arbre
      sinon
         rechercher(fils milieu, mot moins le premier caractère)
   sinon si le premier caractère du mot < le caractère dans la racine, alors
      rechercher(fils gauche, mot)
   sinon
      rechercher(fils droit, mot)

• Écrire une fonction pour faire l'insertion d'un mot dans un arbre ternaire.

Rappelez-vous qu'on ne stocke pas de doublons. Si le mot est déjà présent dans l'arbre, la fonction d'insertion ne fait rien.

Vous pouvez vous baser sur le code de la fonction pour la recherche de l'exercice précédent. Le principal changement est dans le cas où l'arbre est vide mais il reste des caractères du mot à insérer. Dans ce cas, pour la fonction de recherche, le mot n'existe pas dans l'arbre. Par contre, pour la fonction d'insertion, ce cas implique qu'il faut créer des nouveaux noeuds.

• Écrire une fonction qui affiche tous les mots dans l'arbre en ordre lexicographique sur la sortie standard.

Il s'agit d'un parcours en profondeur de l'arbre qui en même temps stocke la partie du mot vue de la racine jusqu'au noeud actuel. Vous pouvez vous inspirer de l'exercice Chemins de la racine aux feuilles du TD 8 et du TP 8.

• Écrire un programme qui lit les mots d'un fichier de texte et qui les insère dans un arbre ternaire. Ensuite, le programme écrit tous les mots lus en ordre lexicographique sur un fichier ou sur la sortie standard. Vous pouvez réutiliser des fonctions de l'exercice 3 du TP 6
• Quel est le 71115ème mot du fichier big.txt dans l'ordre lexicographique ?