trie实现中的字计数

Question

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

TrieNode类的私有部分包括：

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;
}