data-structures - 基本前缀树实现问题

Question

我已经实现了一个基本的前缀树或“trie”。特里树由这样的节点组成：

// pseudo-code
struct node {
    char c;
    collection<node> childnodes;
};

假设我在我的 trie 中添加了以下词：“Apple”、“Ark”和“Cat”。现在，当我查找诸如“Ap”和“Ca”之类的前缀时，我的 trie 的“bool containsPrefix(string prefix)”方法将正确返回 true。

现在我正在实现方法“bool containsWholeWord(string word)”，它将为“Cat”和“Ark”返回true，但为“App”返回false（在上面的示例中）。

trie 中的节点具有某种“endOfWord”标志是否很常见？ 这将有助于确定要查找的字符串是否实际上是输入到 trie 中的整个单词，而不仅仅是前缀。

干杯!

score 2 · Accepted Answer

密钥的结尾通常通过叶节点指示。任何一个：

您的设计没有叶子/空节点。尝试用例如 null 来表示它。

score 1 · Accepted Answer

如果您需要同时存储“App”和“Apple”，而不是“Appl”，那么是的，您需要类似endOfWord标志的东西。

或者，您可以通过（有时）拥有两个具有相同字符的节点来将其放入您的设计中。所以“Ap”必须有子节点：叶节点“p”和一个内部节点“p”和一个子节点“l”。

2 回答 2