ツリーでバックトラッキングを使用する

Question

スタック（プッシュとポップを使用）のおかげでツリーのバックトラッキングアルゴリズムを使用しています。 それは動作しますが、問題があります。スタックによって与えられたパスは「間違っている」。例えば

bool Prefix(Node*root, stack *tas, char *search) 
{ 
    if (!isEmpty(root)) 
    { 
     if (strcmp(search,root->data) != 0) 
      push(tas, root->data, search, root); 

     if (strcmp(search,root->data) == 0) 
     { 
      return True ; 
     } 

     Prefix(root->left, tas, search); 
     Prefix(root->right, tas, search); 
    } 
    return False; 
} 

、私は木を持っている：私は、たとえばCのパスをしたい場合は、この関数はR A B（OK RとA、いないB用）を返し

 Root 
    / \  
    A  B 
/\ /\ 
C D E F  

。

この関数かpush（）関数かどうかはわかりません。 関数にエラーが表示されない場合は、push（）を貼り付けますが、かなり長いです。

編集：私は今理解しています 私は関数に追加しました：
ノードが葉の場合、pop（）。 私がFを検索すると、R B Fの代わりにR A B Fが返されます。Aをスタックに入れないようにする方法は分かりません。

EDIT2：

ここ

コードです：多分 を追加し、私は良い結果を得るために横断子ノードを開くことができますどのように理解していない

bool Prefix(Node*root, stack *tas, char *search) 
{ 
    if (!isEmpty(root)) 
    { 
     if (strcmp(search,root->data) == 0) 
      return True ; 

     if (LeafOrNot(root) == True){ //it's a leaf, pop() 
      pop(tas); 

     if (Prefix(root->left, tas, search)) 
      return True; 
     if (Prefix(root->right, tas, search)) 
      return True; 
    } 
    return False; 
} 

を（RBFのではなく、RABFを返します） a else if（接頭辞（root-> left、tas、search））？誰でもアイデアはありますか？

ありがとうございました！

Answer 1

@マークエリオットに同意する必要がありますが、一見すると、彼の答えは混乱しているようです。停止条件が必要なので、他のノードを探索してスタックに追加しないでください。 boolを返すので、コールがあなたの探しているノードを見つけるかどうかをテストすることができます。

最後のノードをスタックのCへのパスに含める予定だった場合は、スタックに追加するときに文字列比較を削除する必要があります。

たとえば、これを行うことができます。

bool Prefix(Node*root, stack *tas, char *search) 
{ 
    if (!isEmpty(root)) 
    { 
     push(tas, root->data, search, root); 

     if (strcmp(search,root->data) == 0) 
     { 
      return True; 
     } 

     if (Prefix(root->left, tas, search)) 
      return True; 
     if (Prefix(root->right, tas, search)) 
      return True; 
    } 
    return False; 
} 

Answer 2

少なくとも1つの問題は、Prefixへの呼び出しの戻り値をチェックしていないため、再帰呼び出しが「終了」しているかどうかわからないことです。

これはちょうど（あなたのサンプルツリー与えられた）関数呼び出しをウォークスルーさを確認する簡単な方法：これは、呼び出しの順序を示しており、インデントは、コールスタック上のフレームにおおよそに対応

 
Prefix("Root") 
    found "C"? 
    no: Prefix("A") 
     found "C"? 
     no: Prefix("C") 
      found "C"? 
       yes: return true 
     (without check of Prefix("C")): Prefix("D") 
      found "C"? 
       no: return false 
     Prefix("B") 
     found "C"? 
      no: Prefix("E") 
      found "C"? 
       no: return false 
      Prefix("F") 
      found "C"? 
       no: return false 
     return false 
    return false 

。

Prefixへの呼び出しがtrueを返すかどうかをチェックすると、適切なタイミングで終了することができます。