基本前缀树实现问题

我已经实现了基本前缀树或“trie”。这个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中的整个单词而不仅仅是前缀。

干杯！

来源

2011-06-14 MrDatabase

如果您需要同时存储“App”和“Apple”，但不是“Appl”，那么是的，您需要使用endOfWord标志。

或者，您可以通过（有时）具有相同字符的两个节点将其适用于您的设计。因此，“Ap”必须为childnodes：叶节点“p”和内部节点“p”带有子节点“l”。

来源

2011-06-15 12:03:51

密钥的结尾通常通过叶节点表示。可以是：

子节点是空的;或
你有一个分支，有一个关键字的前缀和一些子节点。

您的设计没有叶/空节点。尝试用例如一个null。

来源

2011-06-14 20:17:22

感谢您的回复。不过，我通过检查空的childnodes集合来尝试指示叶节点（就像你提到的那样）。这并不能解决以下问题：将“Apple”插入到trie中。将“Appl”插入到trie中。询问“苹果”是否是一个整体词。在这个例子中（假设你使用上面提到的方法检查叶节点）然而，如果“Appl”是一个完整的单词错误地返回错误，因为“l”不是叶节点。添加“endOfWord”标志修复了这个问题。 – MrDatabase 2011-06-14 20:49:33

基本前缀树实现问题

回答

相关问题