再帰が適切に終了していますか？

Question

TrieNodeとトライオブジェクト：

struct TrieNode { 

    char nodeChar = NULL; 
    map<char, TrieNode> children; 

    TrieNode() {} 
    TrieNode(char c) { nodeChar = c; } 
}; 


struct Trie { 
    TrieNode *root = new TrieNode(); 
    typedef pair<char, TrieNode> letter; 
    typedef map<char, TrieNode>::iterator it; 

    Trie(vector<string> dictionary) { 
     for (int i = 0; i < dictionary.size(); i++) { 
      insert(dictionary[i]); 
     } 
    } 

    void insert(string toInsert) { 
     TrieNode * curr = root; 
     int increment = 0; 
     // while letters still exist within the trie traverse through the trie 
     while (curr->children.find(toInsert[increment]) != curr->children.end()) { //letter found 
      curr = &(curr->children.find(toInsert[increment])->second); 
      increment++; 
     } 
     //when it doesn't exist we know that this will be a new branch 
     for (int i = increment; i < toInsert.length(); i++) { 
      TrieNode temp(toInsert[i]); 
      curr->children.insert(letter(toInsert[i], temp)); 
      curr = &(curr->children.find(toInsert[i])->second); 
      if (i == toInsert.length() - 1) { 
       temp.nodeChar = NULL; 
       curr->children.insert(letter(NULL, temp)); 
      } 

     } 
    } 


    vector<string> findPre(string pre) { 
     vector<string> list; 
     TrieNode * curr = root; 
     /*First find if the pre actually exist*/ 
     for (int i = 0; i < pre.length(); i++) { 
      if (curr->children.find(pre[i]) == curr->children.end()) { //DNE 
       return list; 
      } 
      else { 
       curr = &(curr->children.find(pre[i])->second); 
      } 
     } 
     /*Now curr is at the end of the prefix, now we will perform a DFS*/ 

     pre = pre.substr(0, pre.length() - 1); 
     findPre(list, curr, pre); 

    } 

    void findPre(vector<string> &list, TrieNode *curr, string prefix) { 
     if (curr->nodeChar == NULL) { 
      list.push_back(prefix); 
      return; 
     } 
     else { 
      prefix += curr->nodeChar; 
      for (it i = curr->children.begin(); i != curr->children.end(); i++) { 
       findPre(list, &i->second, prefix); 
      } 

     } 
    } 



}; 

問題は、この機能である：

void findPre(vector<string> &list, TrieNode *curr, string prefix) { 

/*if children of TrieNode contains NULL char, it means this branch up to this point is a complete word*/ 
    if (curr->nodeChar == NULL) { 
     list.push_back(prefix); 
    } 
    else { 
     prefix += curr->nodeChar; 
     for (it i = curr->children.begin(); i != curr->children.end(); i++) { 
      findPre(list, &i->second, prefix); 
     } 

    } 
} 

目的は、DFSを使用してトライから同じプレフィックスですべての単語を返すことです。私はすべての必要な文字列を取得することができますが、私は再帰を終了することはできません。

コードは、if文の最後の繰り返しを完了し、改行します。 Visual Studioはエラーコードを返しません。

Answer 1

再帰の典型的な終わりは、あなたが言った通りです：returnすべての単語。

returnType function(params...){ 
    //Do stuff 
    if(need to recurse){ 
     return function(next params...); 
    }else{ //This should be your defined base-case 
     return base-case; 
} 

問題は、あなたの再帰関数は、それがpush_back実行するか、またはそれが再び自分自身を呼び出すことができますreturn-ことはできませんということで生じ：標準の再帰は次のようになります。これらのどちらも適切に終了していないと思われるので、静かに終了します（何も返されていないと推測されます）。

状況によっては、リストなどの中間構造に再帰の結果を格納し、反復処理後にそのリストを返す必要があります（ツリー検索であり、返されないすべての子をチェックする必要があるため）そのノートオンのみ）

---

最初のものは、あなたは彼らが目的を埋めるために存在するrecursions-のポイントの一部が欠けているように見える。これらの作品は、解決するのは簡単になるまでの部分に問題を打破します。そのケースを返して、完全なソリューションに戻します。どんなツリー検索もこの基本構造から来なければなりません。もしあなたが結果をreturnに忘れてしまったら、何かが見逃されるかもしれません。

Answer 2

Trie構造の完全性をチェックしてください。この関数は正しいと思われます。終了しない理由は、1つ以上のリーフノードにcurr-> nodeChar == NULLがない場合です。

もう1つのケースは、任意のノード（リーフまたは非リーフ）にガベージ・子ノードがあることです。これにより、再帰が読み込みのガベージ値に壊れ、停止する理由はありません。デバッグモードで実行すると、セグメンテーションフォルトで実行が中断されます。

すべてのリーフノードにNULL終了があるかどうかをテストするための別の関数を作成します。

---

EDIT：

コードを掲示した後、元のポスターは、すでに問題は、彼/彼女は、文字列のリストを返していなかったということであったことを指摘しています。

は、それとは別に、私はコードに基づいて提供したいと考え、いくつかのより多くの提案がありますtoInsert文字列がトライにすでにある場合

どのようにこのwhileループは終了しません。 toInsert文字列をオーバーランさせ、ガーベジ文字を読み取ります。 それ以降は終了しますが、文字列を超えて読むことはプログラムするのが悪い方法です。

// while letters still exist within the trie traverse through the trie 
while (curr->children.find(toInsert[increment]) != curr->children.end()) 
{ //letter found 
    curr = &(curr->children.find(toInsert[increment])->second); 
    increment++; 
} 

これは以下のように書くことができる。辞書は、ラージ・オブジェクトとすることができるので

while (increment < toInsert.length() && 
curr->children.find(toInsert[increment]) != curr->children.end()) 

また、

Trie(vector<string> dictionary) 

は

Trie(const vector<string>& dictionary) 

であるべきです。参照渡ししないと、2番目のコピーが作成されます。これは効率的ではありません。

Answer 3

私はばかです。最初のfindPre（）関数でリストを返すのを忘れてしまった。

vector<string> findPre(string pre) { 
    vector<string> list; 
    TrieNode * curr = root; 
    /*First find if the pre actually exist*/ 
    for (int i = 0; i < pre.length(); i++) { 
     if (curr->children.find(pre[i]) == curr->children.end()) { //DNE 
      return list; 
     } 
     else { 
      curr = &(curr->children.find(pre[i])->second); 
     } 
    } 
    /*Now curr is at the end of the prefix, now we will perform a DFS*/ 

    pre = pre.substr(0, pre.length() - 1); 
    findPre(list, curr, pre); 
    return list; //<----- this thing 

}