a. Définissez une classe ''Noeud'' avec les attributs suivants :
+
a. Définissez une classe ''Noeud'' avec les attributs suivants :
-
+
- ''terminal'' : un booléen indiquant si le nœud représente la fin d'un mot.
-
- ''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.
- ''compteur'' : un entier indiquant le nombre d'occurrences du mot.
- ''aretes'' : une liste d'objets de type ''Arete''.
- ''aretes'' : une liste d'objets de type ''Arete''.
-
b. Définissez une classe ''Arete'' avec les attributs suivants :
+
b. Définissez une classe ''Arete'' avec les attributs suivants :
-
+
- ''caractere'' : un caractère représentant la relation entre deux nœuds.
- ''caractere'' : un caractère représentant la relation entre deux nœuds.
- ''noeud'' : un objet de type ''Noeud'' représentant le nœud suivant.
- ''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.
+
c. Pour initialiser un arbre de complétion, créer un nœud vide dont le ''compteur'' vaut 0 et dont la liste des arêtes est une liste (''ArrayList'') vide.
-
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.
+
=== 2. Fonction d'Insertion ===
=== 2. Fonction d'Insertion ===
-
Écrivez une méthode ''insererMot'' dans la classe ''ArbreDeCompletion'' pour insérer un mot dans l'arbre de complétion.
+
Écrivez une méthode ''insererMot'' dans la classe ''Noeud'' pour insérer un mot dans l'arbre de complétion.
-
- La fonction est récursive
+
* La fonction est récursive
-
- Elle prend comme argument une chaîne de caractères
+
* Elle prend comme argument une chaîne de caractères
<note tip>
<note tip>
Ligne 43:
Ligne 40:
* **Cas Récursif** :
* **Cas Récursif** :
On prend le premier caractère du mot (la première lettre) et on cherche une arête dans le nœud actuel qui a ce caractère.
On prend le premier caractère du mot (la première lettre) et on cherche une arête dans le nœud actuel qui a ce caractère.
-
* * S'il existe une telle arête, on appelle récursivement ''insererMot'' avec le nœud correspondant à cette arête et le reste du mot (tous les caractères sauf le premier).
+
* S'il existe une telle arête, on appelle récursivement ''insererMot'' avec le nœud correspondant à cette arête et le reste du mot (tous les caractères sauf le premier).
-
* * Si l'arête n'existe pas, on crée une nouvelle arête avec ce caractère et un nouveau nœud associé. Ensuite, on appelle récursivement ''insererMot'' avec le nouveau nœud et le reste du mot.
+
* Si l'arête n'existe pas, on crée une nouvelle arête avec ce caractère et un nouveau nœud associé. Ensuite, on appelle récursivement ''insererMot'' avec le nouveau nœud et le reste du mot.
</note>
</note>
Ligne 69:
Ligne 66:
=== 3. Fonction d'Affichage ===
=== 3. Fonction d'Affichage ===
-
Écrivez une méthode ''affiche'' dans la classe `ArbreDeCompletion` pour afficher l'arbre de complétion. La fonction doit respecter les conditions suivantes :
+
Écrivez une méthode ''affiche'' dans la classe ''Noeud'' pour afficher la totalité de l'arbre de complétion. La fonction doit respecter les conditions suivantes :
-
+
* Elle doit parcourir l'arbre de manière récursive.
-
- Elle doit parcourir l'arbre de manière récursive.
+
* Elle doit afficher chaque mot complet trouvé ainsi que son compteur.
-
- Elle doit afficher chaque mot complet trouvé ainsi que son compteur.
+
-
4. **Fonction de Suggestion (4 points)**
+
=== 4. Fonction d'Appartenance ===
-
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 :
+
a. Écrivez une méthode ''appartient'' dans la classe ''Noeud'' 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 :
-
+
* Vous pouvez au choix utiliser une approche itérative ou récursive pour parcourir l'arbre.
-
- Elle doit utiliser l'approche de parcours de l'arbre jusqu'au nœud correspondant au préfixe.
+
* La fonction doit retourner ''true'' uniquement si le mot complet est présent dans l'arbre (c'est à dire si la lecture de la dernière lettre conduit à un noeud terminal).
-
- Elle doit trier la liste des mots complets par ordre décroissant de fréquence (compteur).
+
-
5. **Fonction d'Appartenance (3 points)**
+
=== 5. Fonction de Suggestion ===
-
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 :
+
Écrivez une méthode ''suivant'' dans la classe ''Noeud'' pour retourner une liste de mots complets à partir d'un préfixe donné. La fonction doit respecter les conditions suivantes :
-
+
* Elle doit utiliser une approche itérative de parcours de l'arbre jusqu'au nœud correspondant au préfixe.
-
- Utilisez une approche récursive pour parcourir l'arbre.
+
* Elle doit faire appel à la fonction d'affichage du noeud atteint pour afficher l'ensemble des noeuds suivants
-
- La fonction doit retourner `true` uniquement si le mot complet est présent dans l'arbre.
+
-
6. **Tests Unitaires (3 points)**
+
=== 6. Tests ===
-
a. Créez un arbre de complétion vide.
+
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.
+
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.
+
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.
+
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.
+
e. Testez la fonction ''appartient'' avec les mots ''"chat"'', ''"maison"'', et ''"bon"'', 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.