Trie只插入一个单词的第一个字母，而不是整个单词

Question

我目前正在编写一个程序，我将单词插入到trie中。目前我的插入功能只添加在单词的第一个字母，然后停止。从我查找的所有内容中，我的代码看起来都是正确的，所以我不明白问题是什么。

我已经尝试将temp-> wordEnd = true移动到for循环的外部以及函数中的不同位置。因为我认为这是问题，因为我的插入函数中的其他内容看起来都是正确的。

这是我的插入功能：

bool Trie::insert(string word)
{
    TrieNode *temp = root;
    temp->prefixAmount++;

    for (int i = 0; i < word.length(); ++i)
    {
        int currentLetter = (int)word[i] - (int)'a';
        if (temp->child[currentLetter] == NULL)
        {
            temp->child[currentLetter] = new TrieNode();
            temp->child[currentLetter]->prefixAmount++;
            temp = temp->child[currentLetter];
        }
        temp->wordEnd = true;
        return true;
    }
}

还要帮助每个人更好地遵循我的代码这是我的TrieNode结构：

  struct TrieNode
   {
     int prefixAmount;
     struct TrieNode *child[ALPHA_SIZE];
    bool wordEnd;

   };

这是我的Trie构造函数：

   Trie::Trie()
    {
      root = new TrieNode();
      root->wordEnd = false;
     root->prefixAmount = 0;

     }

预期的结果应该是整个世界都被插入。实际发生的是只添加了单词的第一个字母。

Answer 1

我为你重新格式化了代码，现在你应该看到主要的问题。

你在for循环中的块的末尾返回。这意味着它运行for循环的第一次迭代，只返回而不考虑其余的字母。

一个简单的解决方法是将返回放在for循环之外，但是如果当前字母已经在其中，则还有另一个问题就是你没有正确更新Trie。你的NULL检查是正确的，但你应该只在new上NULL上升TrieNode，但你也想要运行所有后续行，即使它不是NULL。固定代码如下：

bool Trie::insert(string word)
{
    TrieNode *temp = root;
    temp->prefixAmount++;

    for (int i = 0; i < word.length(); ++i)
    {
        int currentLetter = (int)word[i] - (int)'a';
        if (temp->child[currentLetter] == NULL)
        {
            temp->child[currentLetter] = new TrieNode();
        }
        temp->child[currentLetter]->prefixAmount++;
        temp = temp->child[currentLetter];
    }
    temp->wordEnd = true;
    return true;
}

（问题范围之外的代码中的其他小问题 - 更喜欢nullptr到NULL，为什么返回bool，如果它总是true，如果你的字符串包含a-z以外的任何东西那么你将读出数组边界之外，更喜欢unique_ptr和make_unqiue原始new / delete）。