1

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

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

たとえば、次のようなツリーがあります。

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

たとえば、C のパスが必要な場合、この関数は RAB を返します (B ではなく R と A でOK)。

この関数によるものなのか、push() 関数によるものなのかはわかりません。関数にエラーが表示されない場合は、push() を貼り付けますが、かなり長いです。

編集：私は今、よりよく理解しています。関数に追加しました：
ノードがリーフの場合、pop（）。F を検索すると、RB F ではなく RABF が返されます。A をスタックに保持しないようにする方法がわかりません。

edit2 :

コードは次のとおりです: (RBF の代わりに RABF を返します)

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

if (Prefix(root->left, tas, search)) にelseを追加して、トラバースする子ノードをポップして良い結果を得る方法がわかりません。誰にもアイデアがありますか？

ありがとう ！

4

2 に答える 2

3

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

これを確認する簡単な方法は、関数呼び出しをウォークスルーすることです (サンプル ツリーが与えられます)。

Prefix("ルート")
  「C」を見つけましたか？
    いいえ: プレフィックス("A")
      「C」を見つけましたか？
        いいえ: プレフィックス("C")
           「C」を見つけましたか？
              はい: true を返します
        (Prefix("C")のチェックなし): Prefix("D")
           「C」を見つけましたか？
              いいえ: false を返します
      プレフィックス("B")
        「C」を見つけましたか？
          いいえ: プレフィックス("E")
             「C」を見つけましたか？
               いいえ: false を返します
          プレフィックス("F")
             「C」を見つけましたか？
               いいえ: false を返します
       false を返す
  false を返す

これは、コールとインデントの順序がコール スタックのフレームにほぼ対応していることを示しています。

return の呼び出しによって適切なタイミングで終了できるPrefixかどうかを確認する場所を確認できます。true

于 2011-07-07T00:03:55.470 に答える
2

@Mark Elliotに同意する必要がありますが、一見すると、彼の答えは混乱しているように見えるかもしれません. 他のノードを探索してスタックに追加し続けないように、停止条件が必要です。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;
}
于 2011-07-07T00:38:46.463 に答える