Nombre de mots
Leçon 9 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
Combien de mots distincts se trouvent dans ce trie en ce moment ? Il n'y a pas de compteur global, nous devons donc parcourir l'arbre et compter les nœuds où isEndOfWord est true.
Un parcours en profondeur commençant à la racine fait le travail en un seul passage. Pour chaque nœud, ajoutez 1 s'il s'agit d'une fin de mot, puis effectuez une récursion dans chaque enfant et additionnez les résultats. Le total correspond au nombre de mots stockés.
Remarquez que cela gère naturellement les doublons : insérer "cat" trois fois marque toujours un seul nœud comme fin de mot, donc le compte est de 1. Les préfixes qui n'ont jamais été insérés en tant que tels ne sont pas comptés non plus - leurs nœuds existent, mais isEndOfWord est false pour eux.
Défi
FacileAjoutez une méthode wordCount à la classe Trie.
Elle ne prend aucune entrée et renvoie le nombre de mots distincts actuellement stockés dans le trie. Parcourez le trie à partir de la racine et comptez chaque nœud dont isEndOfWord est true.
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "delete") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_delete(&t, arg); }
if (strcmp(cmd, "wordCount") == 0) { printf("%d\n", Trie_wordCount(&t)); }
}
return 0;
}