c++ - 打印出用 map 实现的 Trie 中的所有单词

Question

我有一个 TrieNode 类定义如下:

class TrieNode {
public:
    map<char, TrieNode*> children;
    bool isLeaf = false; // if node represents end of word
    int wordCount = 0; // How many times the word appears
    TrieNode();
};

我正在尝试打印出 trie 中的所有单词(最好按字母顺序排列，尽管此时我会接受任何东西)。我一直在尝试实现一个递归解决方案，但我一直没能有一个像样的开始。

编辑:我应该提一下，我研究过的所有其他问题都是关于如何将 trie 中的所有单词打印为数组而不是 map 。

Answer 1

这是一个深度优先的递归遍历。 最好不要使用原始指针，但我在这里这样做是因为你问了，我喜欢你。 我没有删除AddTrie分配的子节点，因为我只是想演示遍历，而不是写一个完整的实现。 所以，如果你使用这个，你需要添加代码来删除它们。

#include <iostream>
#include <map>
#include <string>

class TrieNode {
public:
    std::map<char, TrieNode*> children;
    bool isLeaf = false; // if node represents end of word
    int wordCount = 0; // How many times the word appears
    TrieNode() {}
};

void AddTrie(TrieNode& trie, const char* word) {
    auto c = *(word++);
    auto next = trie.children[c];
    if(!next) { trie.children[c] = next = new TrieNode; }
    if(*word) { AddTrie(*next, word); }
    else      { next->isLeaf = true; }
}

void DumpTrie(const TrieNode& trie, std::string word={}) {
    for(const auto& child : trie.children) {
        const auto next_word = word + child.first;
        if(child.second->isLeaf) { std::cout << next_word << '\n'; }
        DumpTrie(*child.second, next_word);
}   }

int main() {
    TrieNode trie;
    AddTrie(trie, "goodbye");
    AddTrie(trie, "hello");
    AddTrie(trie, "good");
    AddTrie(trie, "goodyear");
    DumpTrie(trie);
}

输出

good
goodbye
goodyear
hello