深度優先搜索

Question

我有一個後綴樹，這棵樹的每個節點是一個結構

struct state { 
int len, link; 
map<char,int> next; }; 
state[100000] st; 

我需要爲每個節點DFS和得到，我可以接觸到所有的字符串，但我不知道如何製作。 這是我的DFS功能

void getNext(int node){ 
    for(map<char,int>::iterator it = st[node].next.begin();it != st[node].next.end();it++){ 
     getNext(it->second); 
} 
} 

這將是完美的，如果我能像

map<int,vector<string> > 

其中int是我的樹和矢量串的節點，我可以達到

現在它的工作原理

void createSuffices(int node){//, map<int, vector<string> > &suffices) { 
if (suffices[sz - 1].size() == 0 && (node == sz - 1)) { 
    // node is a leaf 
    // add a vector for this node containing just 
    // one element: the empty string 
    //suffices[node] = new vector<string> 
    //suffices.add(node, new vector<string>({""})); 
    vector<string> r; 
    r.push_back(string()); 
    suffices[node] = r; 
} else { 
    // node is not a leaf 
    // create the vector that will be built up 
    vector<string> v; 
    // loop over each child 
    for(map<char,int>::iterator it = st[node].next.begin();it != st[node].next.end();it++){ 
     createSuffices(it->second); 
     vector<string> t = suffices[it->second]; 
     for(int i = 0; i < t.size(); i ++){ 
      v.push_back(string(1,it->first) + t[i]); 
     } 
    } 
    suffices[node] = v; 
} 
} 

Answer 1

您可以通過map<int, vector<string>>來獲得她與你的深度第一次搜索。當遞歸調用從某個節點n返回時，您知道該節點的所有足夠的準備就緒。我的C++技能是太有限了，所以我會在僞代碼寫：

void createSuffices(int node, map<int, vector<string>> suffices) { 
    if (st[node].next.empty()) { 
     // node is a leaf 
     // add a vector for this node containing just 
     // one element: the empty string 
     suffices.add(node, new vector<string>({""})); 
    } else { 
     // node is not a leaf 
     // create the vector that will be built up 
     vector<string> v; 
     // loop over each child 
     foreach pair<char, int> p in st[node].next { 
      // handle the child 
      createSuffices(p.second, suffices); 

      // prepend the character to all suffices of the child 
      foreach string suffix in suffices(p.second) { 
       v.add(concatenate(p.first, suffix)); 
      }     
     } 
     // add the created vector to the suffix map 
     suffices.add(node, v); 
    } 
}