递归 - >迭代

Question

用下面Trie树结构：

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

我使用以下代码来提取一个线索字转换为按字母顺序的载体。

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

这些状态是一个显式堆栈，跟踪递归跟踪的相同数据，非常多。我想我设法按照递归函数的顺序访问元素，但这并不重要。

请注意，上面的代码是写入并未经过测试，并且您必须为状态编写一个元素明确的构造函数，因为我很懒。