如何遍历一个trie来显示所有的单词？

Question

这是我在 C++ 中使用 unordered_map

声明的 trie

class trie{
    public:
    unordered_map<char,trie*>m;
    bool isEnd;
};

这是我的插入函数（另一个 class 的一部分）

 trie *root=nullptr;
    trie *getNode()
    {
        trie *tmp=new trie();
        tmp->isEnd=false;
        return tmp;
    }
    void insert(string s)
    {
        if(!root)
            root=getNode();
    trie *tmp=root;
    for(int i=0;i<s.length();i++)
    {
        if(tmp->m.find(s[i])==tmp->m.end())
            tmp->m[s[i]]=getNode();
        tmp=tmp->m[s[i]];
    } 
    tmp->isEnd=true;
    }

如何递归或迭代遍历这个trie来显示所有的单词。

Answer 1

void iterate_(const trie* node, const std::string& prefix) {
  if (node->isEnd) {
    std::cout << prefix << std::endl;
  }
  for (const auto& [c, child] : node->m) {
    iterate_(child, prefix + c);
  }
}

void iterate() {
  if (root) {
    iterate_(root, "");
  }
}

如何遍历一个trie来显示所有的单词？

How to traverse a trie to display all the words?

c++

stl

trie

data-structures