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

Question

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

这就是我实现 TrieNode 的方式。

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

我知道我可以存储一个指向父节点的指针，深度优先搜索所有isWord==True 的节点并递归地打印这些节点中的每个单词。

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

感谢您的帮助。

Answer 1

这是 Konrad Rudolph 的一个相当有效的版本，没有假设数据是一个字符。我还以使用 std::string& 为代价删除了 Konrad 版本中分配的 O(n^2) 总内存。这个想法是传递前缀并在每次递归时修改它，将字符推到最后并在之后弹出它，最终比疯狂复制它稍微高效一些。

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