c++ - 递归 -> 迭代

Question

使用以下 Trie 结构:

struct Trie{
    char letter;
    bool eow;
    Trie *letters[26];
};

我正在使用以下代码将单词从 trie 中提取到按字母顺序排列的 vector 中。

void getWords(const TrieNode& data, vector<string> &words, string acc)
{
  if (data.eow)
    words.push_back(acc);

  for (int i = 0; i < 26; i++) {
    if (data.letters[i] != NULL)
      getWords(*(data.letters[i]), words, acc + data.letters[i]->letter);
  }
}

我只是想知道是否有一种方法可以不用递归，只使用迭代来做到这一点？我试图仅通过迭代来实现这一点，但想不出一种方法来使用循环检查 trie 中每一层的每个字母。有什么建议吗？

Answer 1

struct State {
  const TrieNode* data;
  string acc;
  int index;
  State( ... ): ... {} // element-wise constructor, left as an exercise
};

std::vector<string> getWords( const TrieNode* root )
{
  std::vector<string> retval;
  std::vector<State> states;
  states.push_back( State( root, string(), 0 ) );
  while (!states.empty())
  {
    State s = states.back();
    states.pop_back();
    if (s.data->eow)
    {
      retval.push_back( s.acc );
      continue;
    }
    if (s.index >= 26)
      continue;
    states.push_back( State( s.data, s.acc, s.index+1 ) );
    if (s.letters[s.index])
    {
      states.push_back( State( s.letters[s.index], s.acc + s.letters[s.index]->letter, 0 ) );
    }
  }
  return std::move(retval);
};

状态是一个显式堆栈，它跟踪的数据与您递归跟踪的数据几乎相同。我想我设法以与递归函数相同的顺序访问元素，但这并不重要。

请注意，上面的代码是编写的，没有经过测试，你必须为State 编写一个element-wise 构造函数，因为我很懒。