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

Question

我正在尝试Trie用C++ 创建一个实现.我无法弄清楚如何打印存储在中的所有单词Trie.

这就是我实现的方式TrieNode.

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

我知道我可以将a存储pointer到父节点,Depth-First搜索所有节点,isWord==True然后从这些节点递归打印每个单词.

但我想知道有没有办法打印出Trie我的实现中的每个单词TrieNode.

谢谢你的帮助.

Answer 1

这是一个相当有效的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();
    }
  }
}

Answer 2

您不需要父节点,您的代码可以通过递归轻松适应遍历.伪代码:

void traverse(string prefix, TrieNode const& n) {
    prefix += static_cast<char>(n.data);

    if (n.isWord)
        print(prefix);

    for (auto const next : n.Child)
        if (next)
            traverse(prefix, *next);
}

这或多或少都是有效的C++.只需print适当定义.

编辑为了回应Yakk的评论和你的澄清,这里的版本不假设data包含当前字符(我的错误!):

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

    for (std::size_t i = 0; i < ALPHABET_SIZE; ++i)
        if (n.child[i])
            traverse(prefix + ('a' + i), *n.child[i]);
}

我将把更有效的实现留给Yakk的回答.