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

Question

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

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

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

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

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

干杯!

Answer 1

键的结束通常通过叶节点来指示。要么:

• 子节点为空；或
• 您有一个分支，带有一个键前缀和一些子节点。

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