0

私はこれの論理に問題があります。ツリー全体を検索して (順序検索に頼ることができないため)、一致する値を 1 つだけ返す (存在する場合) にはどうすればよいですか? 再帰呼び出しを返すと、最初のリーフにヒットして一致が見つからないと失敗しませんか?

以下の関数を使用すると、一致が見つかるかツリーの最後に到達するまで呼び出しが行われ、一致に関係なく最も左のノードが返されます。

順番にトラバースする私の再帰関数：

tnode *find(tnode *ptr, const char *str)
{
    if (ptr == NULL) return ;

    if(strcmp (str,ptr->str) == 0)
        return ptr;


    else 
    {
        //search left subtree
        if (ptr->left != NULL)
            find(ptr->left, str) ;


        // search right subtree
        if (ptr->right != NULL)
            find(ptr->right, str) ;
    }

   return;

}
4

2 に答える 2

2

最初：

if (ptr == NULL) return ;

関数プロトタイプ ( ) に従って値を返すことになっていますtnode *find(tnode *ptr, const char *str)。

二番目：

find(ptr->right, str);

戻り値を使用しないため、とにかく結果は正しくありません。

第3：

return;

最初と同じ。

それをすべて修正すれば、うまくいくはずです。

関数の最初にチェックしているので、 BTWif (ptr->left != NULL)は必要ありません。ptr == 0

最後の 1 つは、コンパイラの警告に注意してください。

于 2013-04-22T14:24:32.790 に答える
1

左サブツリーの検索で非 NULL が返された場合、一致があり、それを返す必要があります。現在、何かが見つかったかどうかを確認することさえありません。

何も見つからなかった場合は、右サブツリー検索の結果を返すことができます (NULL の場合は、どこを探しても何も見つかりませんでした)。

tnode *find(tnode *ptr, const char *str)
{
    ptr *found;

    if (ptr == NULL) return NULL; /* nothing to see here */

    if(strcmp (str,ptr->str) == 0)
        return ptr; /* it is here! */

    /* try left subtree */
    found = find(ptr->left, str);
    if (found) return found; /* it was on the left */

    /* try right subtree */
    return find(ptr->right, str);
}
于 2013-04-22T14:23:27.263 に答える