c++ - 如何在Trie中打印所有单词？

我正在尝试在C++中创建Trie实现。我不知道如何打印存储在Trie中的所有单词。

这就是我实现TrieNode的方式。

struct TrieNode{
  bool isWord;
  int data; //Number of times Word Occured
  TrieNode *Child[ALPHABET_SIZE]; //defined as 26
};

我知道我可以将pointer存储到父节点，即深度优先搜索所有节点，其中isWord==True并递归打印这些节点中的每个单词。

但是我想知道是否有一种方法可以实现Trie来打印TrieNode中的每个单词。

谢谢你的帮助。

最佳答案

这是Konrad Rudolph的一个相当有效的版本，没有假定数据是字符。我还删除了Konrad版本中分配的O(n ^ 2)总内存，但使用了std::string&。这个想法是传递前缀并在每次递归中对其进行修改，将字符推到末尾，然后弹出它，这比疯狂复制它的效率更高。

void traverse(std::string& prefix, TrieNode const& node) {
  if (node.isWord)
    print(prefix);

  for (char index = 0; index < ALPHABET_SIZE; ++index) {
    char next = 'a'+index;
    TrieNode const* pChild = node.Child[index];
    if (pChild) {
      prefix.push_back(next);
      traverse(prefix, *pChild);
      prefix.pop_back();
    }
  }
}