Un algorithme de complétion est un mécanisme logique permettant d'anticiper la saisie et de proposer des mots automatiquement pour faciliter les recherches dans un formulaire sur une page web par exemple.

On utilise pour cela une structure de données arborescente, où chaque nœud de l'arbre est une étape de lecture et chaque arête correspond à la lecture d'une lettre. Les nœuds sont indexés par les lettres suivantes possibles du mot, avec un compteur par nœud pour savoir si celui-ci est final ou non (le nœud est final si le compteur est >0).

Le but de cet exercice est de construire un arbre de complétion à partir de mots de vocabulaire, puis de l'utiliser pour compléter un début de mot proposé par l'utilisateur.

Vous devez implémenter un arbre de complétion en Java pour gérer une base de mots et répondre à différentes requêtes, telles que l'insertion de mots, l'affichage de l'arbre, la suggestion de mots complets à partir d'un préfixe donné, etc.

 a. Définissez une classe ''Noeud'' avec les attributs suivants :
 
    - ''estTerminal'' : un booléen indiquant si le nœud représente la fin d'un mot.
    - ''compteur'' : un entier indiquant le nombre d'occurrences du mot.
    - ''aretes'' : une liste d'objets de type ''Arete''.

 b. Définissez une classe ''Arete'' avec les attributs suivants :
 
    - ''caractere'' : un caractère représentant la relation entre deux nœuds.
    - ''noeud'' : un objet de type ''Noeud'' représentant le nœud suivant.

 c. Définissez une classe ''ArbreDeCompletion'' avec un nœud racine comme attribut.
 Dans le constructeur, créer un nœud vide le ''compteur'' vaut 0 et dont la liste des arêtes est une liste (''ArrayList'') vide. 

Écrivez une méthode insererMot dans la classe ArbreDeCompletion pour insérer un mot dans l'arbre de complétion.

1. La fonction est récursive
2. Elle prend comme argument une chaîne de caractères

String mot = "bonjour";
char premierCaractere = mot.charAt(0);

String mot = "bonjour";
String resteDuMot = mot.substring(1);

Écrivez une méthode affiche dans la classe `ArbreDeCompletion` pour afficher l'arbre de complétion. La fonction doit respecter les conditions suivantes :

 
    - Elle doit parcourir l'arbre de manière récursive.
    - Elle doit afficher chaque mot complet trouvé ainsi que son compteur.

4. Fonction de Suggestion (4 points)

 a. Écrivez une fonction `suivant` dans la classe `ArbreDeCompletion` pour retourner une liste de mots complets à partir d'un préfixe donné. La fonction doit respecter les conditions suivantes :
 
    - Elle doit utiliser l'approche de parcours de l'arbre jusqu'au nœud correspondant au préfixe.
    - Elle doit trier la liste des mots complets par ordre décroissant de fréquence (compteur).

5. Fonction d'Appartenance (3 points)

 a. Écrivez une fonction `appartient` dans la classe `ArbreDeCompletion` qui retourne `true` si le mot est présent dans l'arbre de complétion et `false` sinon. La fonction doit respecter les conditions suivantes :
 
    - Utilisez une approche récursive pour parcourir l'arbre.
    - La fonction doit retourner `true` uniquement si le mot complet est présent dans l'arbre.

6. Tests Unitaires (3 points)

 a. Créez un arbre de complétion vide.
 
 b. Insérez les mots "chat", "chien", "chapeau", "bonjour", "bonsoir", "bon", "jour", "soir" dans l'arbre de complétion.
 
 c. Affichez l'arbre pour vérifier que les mots sont correctement insérés.
 
 d. Testez la fonction `suivant` avec le préfixe "bon" et affichez les résultats.
 
 e. Testez la fonction `appartient` avec les mots "chat", "maison", et "bonsoir", affichez le résultat pour chaque test.

### Note :

- La clarté, la concision et la logique de votre code seront pris en compte. - Assurez-vous de respecter les contraintes spécifiées dans chaque question. - Indiquez toute hypothèse que vous faites dans votre réponse.

—