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

Question

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

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

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

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

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

干杯!

Answer 1

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

或者，您可以通过(有时)具有两个具有相同字符的节点来将其融入您的设计中。所以“Ap”必须对子节点:叶节点“p”和带有子节点“l”的内部节点“p”。