Trie树结构声明

Question

所以我有一段代码(不是我的)，我无法理解这些结构是什么样子的。有人能解释一下吗？

typedef struct trie_node trie_node_t;
struct trie_node
{
    int value;
    trie_node_t *children[ALPHABET_SIZE];
};

// trie ADT
typedef struct trie trie_t;
struct trie
{
    trie_node_t *root;
    int count;
};

在第二个结构中的Int计数是用来计数树中所有的单词，但是我想知道每个单词在里面放了多少次，除了修改代码的其余部分之外，我应该如何修改结构来实现这一点呢？

代码的其余部分：http://pastebin.com/9zQuCBjb

Answer 1

我想您很熟悉trie的概念，您可以通过遍历(或爬行，使用链接代码中的单词)在树上使用单词的字母，并根据找到的字母在每个节点分支来查找单词和前缀。每个节点都有许多子节点；如果使用不区分大小写的拉丁字母，则为26。

这个词被编码在你到达的路径上：

root->[f]->[i]->[s]->[h]  --> "fish"

现在，您需要知道当前节点是否代表一个单词。"fish"是一个单词，但"fis"不是。您不能使用节点是一个没有子节点的叶的事实，因为"fishbone"可能在字典中。这就是value条目的含义:零表示当前节点不表示单词，否则值是当前单词的一个基于一个的索引。

当您创建一个新条目时，您只需沿着trie爬行，可能会在执行过程中创建新节点，并使用当前单词计数作为值标记最后一个节点。如果"fishbode"已经在trie中，并且添加了"fish"，则不会创建新节点，只会用新值标记"h"节点。

trie结构只是一个助手，用于包含trie的根节点和计数。

如果希望跟踪发生的情况，请向节点添加一个count字段，并在设置value时增加该字段。(原始代码不检查一个值以前是否已经在trie中，而是无条件地添加单词，从而覆盖任何旧值。)

您还可以通过在插入密钥时传递节点时，有一个prefix_count字段并将其递增，从而保持以当前节点前缀开头的所有单词的计数。

当您想要检索事件时，您必须遍历所有子树。

尝试对于用户输入的第一个字母或T9风格的打字系统中的单词自动扩展很有用，但它们相当贪心记忆。如果您只想计算单词出现的次数(而不使用trie的好处)，那么使用一个单词的散列图来计数可能会更容易。