Conteo de palabras
Lección 9 de 14 del curso Tries - Serie de Estructuras de Datos #8 de Coddy.
¿Cuántas palabras distintas viven en este trie en este momento? No hay un contador acumulativo, por lo que tenemos que recorrer el árbol y contar los nodos donde isEndOfWord es true.
Una búsqueda en profundidad (depth-first search) comenzando en la raíz realiza el trabajo en una sola pasada. Para cada nodo, suma 1 si es el final de una palabra, luego realiza la recursión en cada hijo y suma los resultados. El total es el número de palabras almacenadas.
Observa que esto maneja los duplicados de forma natural: insertar "cat" tres veces sigue marcando un solo nodo como final de palabra, por lo que la cuenta es 1. Los prefijos que nunca se insertaron por derecho propio tampoco se cuentan; sus nodos existen, pero isEndOfWord es false en ellos.
Desafío
FácilAgrega un método wordCount a la clase Trie.
No recibe ninguna entrada y devuelve el número de palabras distintas almacenadas actualmente en el trie. Recorre el trie desde la raíz y cuenta cada nodo cuyo isEndOfWord sea true.
Pruébalo tú mismo
#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;
}