单词数量

Coddy 字典树：数据结构系列第 8 课课程的第 9 课，共 14 课。

现在这个字典树中有多少个不同的单词？我们没有计数器，所以必须遍历这棵树，统计 isEndOfWord 为 true 的节点。

从根节点开始进行深度优先搜索，一次遍历就能完成。对于每个节点，如果它是单词的结尾，就加 1，然后递归遍历每个子节点并累加结果。总数就是存储的单词数。

注意，这种方法会自然地处理重复项：即使插入 "cat" 三次，也只会将一个节点标记为单词的结尾，因此计数为 1。那些从未单独插入的前缀也不会被计入，它们的节点虽然存在，但 isEndOfWord 为 false。

挑战

简单

在 Trie 类中添加一个 wordCount 方法。

它不接收输入，并返回当前存储在字典树中的不同单词数量。从根节点遍历字典树，统计每个 isEndOfWord 值为 true 的节点。

亲手试试

#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;
}

字典树：数据结构系列第 8 课中的所有课

1简介

简介什么是 Trie？

2Trie 项目

TrieNode 类 Trie 类插入搜索判断前缀删除单词数量

3挑战练习

最长公共前缀统计前缀匹配的单词自动补全字典中的最长单词单词拆分

自己练习： C 在线编译器