如何在Trie中打印所有单词？ [英] How to print all words in a Trie?

问题描述

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

I am trying to create a Trie Implementation in C++. I cannot figure out how to print all words stored in the Trie.

这是我如何实现 TrieNode 。

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

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

I know I could store a pointer to the parent node, Depth-First Search for all nodes where isWord==True and recursively print each word from those nodes.

但是我想知道有没有办法打印出 Trie 中的每个单词，而我的执行 TrieNode 。

But I'm wondering is there a way to print out each word in the Trie with my implementation of a TrieNode.

感谢任何帮助。

推荐答案

一个合理有效的版本的康拉德·鲁道夫（Konrad Rudolph），不假定数据是一个字符。我还删除了Konrad版本中分配的O（n ^ 2）总内存，其代价是使用 std :: string& 。这个想法是传递前缀并在每次递归时进行修改，将字符推到最后，然后将其弹出，最终比复制它的效率略高一些。

Here is a reasonably efficient version of Konrad Rudolph, without assuming data is a character. I also removed the O(n^2) total memory allocated in Konrad's version at the cost of using a std::string&. The idea is to pass down the prefix and modify it at each recursion, pushing characters onto the end and poping it afterwards, ends up being slightly more efficient than copying it madly.

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

这篇关于如何在Trie中打印所有单词？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！