I'm implementing a trie to implmenta spelling dictionary. The basic element of a trie is a trienode, which consists of a letter part (char), a flag(whether this char is the last char of a word), and an array of 26 pointers.
Private part of the TrieNode class include:
ItemType item;//char
bool isEnd;//flag
typedef TrieNode* TrieNodePtr;
TrieNodePtr myNode;
TrieNodePtr array[26];//array of pointers
This is part of the test call:
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;
Right now I'm trying to traverse the trie to count how many words there are (how many flags are set to 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
}
}
}
Every time the function returns 0. I know it's because when the first element in the array is null, then the function exits, so the count is always 0. But I don't know how to avoid this, since every time I have start from the first pointer. I also get a warning:not all control paths return a value. I'm not sure where this comes from. How do I make the function continue to the next pointer in the array if the current pointer is null? Is there a more efficient way to count words? Thank you!
Here is a simple and clear way to do it(using depth-first search):