1

使用以下 Trie 结构：

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

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

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 中每一层的每个字母。有什么建议么？

4

1 回答 1

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

The states is an explicit stack that tracks the same data as you tracked recursively, pretty much. I think I managed to visit the elements in the same order your recursive function would, but that wouldn't really matter.

Note that the above code is written and not tested, and you have to write an element-wise constructor for State, because I'm lazy.

于 2012-10-27T20:22:26.887 回答