c++ - 插入到 Trie 中，NULL 指针

Question

我有一个关于 Trie 数据结构的具体问题以及我的代码出了什么问题。当我递归调用 insert 时，函数参数 root 始终为 NULL。这是我的代码:

代码:

//subNodes is an array of TrieNode pointers that contains indices for all letters in the alphabet

bool insert(const string& word, TrieNode* root, int curI = 0)
//PRE:  word must be a valid word in a dictionary
//POST: True when a word is inserted into the Trie, false otherwise
{
    if(curI >= word.length())        //word has been scanned fully
    {
        root->isWord = true;
        return true;
    }
    else                             //word has more letters to be scanned
    {
        if(root->subNodes[word[curI] - 'A'] == NULL)    //if the current letter of the word is not in the trie
        {                                            //   insert the letter and advance the current letter of the word
            root->subNodes[word[curI] - 'A'] = new TrieNode(word[curI]);
            insert(word, root->subNodes[word[curI] - 'A'], curI++);
        }
        else                                         //if the currrent letter of the word is in the trie
        {                                            //   advance the current letter of the word
            insert(word, root->subNodes[word[curI] - 'A'], curI++);
        }
    }

}

我通过将 subNodes[word[curI] - 'A'] 替换为 subNodes[word[13]] (13是字母表中 N 的索引，我正在测试单词 not) 并且根不再是该调用的 NULL。因此索引出了问题。有谁知道出了什么问题？我考虑过使用 C++ 映射或 vector 。有人对使用数组有异议吗？

Answer 1

您是说 ++curl - 即将递增的值传递给递归调用吗？由于 curl++ 是后递增的，因此您将向每个递归传递相同的值。无论如何，只写 curl + 1 可能更容易，因为您不再需要 curl 值。