基本前缀树实现问题

Question

我实现了一个基本的前缀树或"trie“。trie由如下节点组成：

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

说我在我的旅行中添加了以下几个词："Apple“、"Ark”和"Cat“。现在，当我查找前缀"Ap“和"Ca”时，我的trie的"bool containsPrefix(字符串前缀)“方法将正确返回true。

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

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

干杯!

Answer 1

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

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

Answer 2

键的结尾通常是通过叶节点来表示的。以下任一项：

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

您的设计没有叶/空节点。试着用空来表示它。