c++ - 在 trie 实现中计算单词

Question

我正在实现一个 trie 以实现拼写字典。一个trie节点的基本元素是一个trienode，它由一个字母部分(char)、一个标志(这个字符是否是一个单词的最后一个字符)和一个26个指针组成的数组组成。

TrieNode 类的私有(private)部分包括:

ItemType item;//char
bool isEnd;//flag
typedef TrieNode* TrieNodePtr;
TrieNodePtr myNode;
TrieNodePtr array[26];//array of pointers

这是测试调用的一部分:

Trie t4 = Trie();
t4.insert("for");
t4.insert("fork");
t4.insert("top");
t4.insert("tops");
t4.insert("topsy");
t4.insert("toss");
t4.print();
cout << t4.wordCount() << endl;

现在我正在尝试遍历 trie 以计算有多少单词(有多少标志设置为 true)。

size_t TrieNode::wordCount() const{
    for (size_t i = 0; i < 26; i++){
        if (array[i] == nullptr){
            return 0;
        }
        if (array[i]->isEnd && array[i] != nullptr){
            cout << "I'm here" << endl;
            return 1 + array[i]->wordCount();
        }
        else if(!array[i]->isEnd && array[i]!=nullptr){
            cout << "I'm there" << endl;
            return 0 + array[i]->wordCount();
        }
        else{
            // do nothing
        }
    }
}

每次函数返回0。我知道这是因为当数组中的第一个元素为null时，函数退出，所以计数总是0。但我不知道如何避免这种情况，因为每次我从第一个指针开始。我还收到警告:并非所有控制路径都返回值。我不确定这是从哪里来的。如果当前指针为空，如何使函数继续到数组中的下一个指针？有没有更有效的方法来计算单词？谢谢!

Answer 1

这是一个简单明了的方法(使用深度优先搜索):

size_t TrieNode::wordCount() const {
    size_t result = isEnd ? 1 : 0;
    for (size_t i = 0; i < 26; i++){
        if (array[i] != null)
            result += array[i]->wordCount();
    return result;
}