1


再帰関数を使用して、二分木 (いいえ、二分検索木ではなく、単なる二分木) を使用した検索方法を作成しようとしています。データが二分木上にある場合はノードを返し、そうでない場合はNULL値を返します。検索機能を作成しましたが、その機能は完璧です。しかし問題は、関数がノードを返さないように見えることです。

struct二分木の場合は次のとおりです。

struct data
{
    int number;
    struct data *left, *right;
}*root = NULL;

そして、これは私が話している検索機能です:

data* search(struct data *node, int key)
{
    if(node == NULL)
        return NULL;
    else
    {
        printf("\n%d %d -", node->number, key);

        if(node->number== key)
            return node;

        search(node->left, key);
        search(node->right, key);
    }
}

このように検索関数を呼び出している場合: 、数値を二分木にプッシュしたにもかかわらず、値search(root, 6);を返していると表示されます(検索関数もその行で停止するため、関数がを返します。)NULL6return node;NULL

ここでバイナリツリーのチュートリアルを見て、 そこからいくつかのコードを使用して変更しましたが、それでも同じです。私はここで必死に助けを求めています:(

4

4 に答える 4

4

NULL最上位ノードにキーが含まれている場合を除き、関数は常に を返します。関数は、再帰呼び出しの結果に対して何もしません。return実際、制御フローは、ステートメントにヒットすることなく、その「最後に落ちる」可能性があります。

再帰呼び出しからの戻り値を確認し、必要に応じてそれらを渡す必要があります。

if (node == NULL)
    return NULL;
else if (node->number == key)
    return node;
else {
    data *left = search(node->left, key);
    return left? left: search(node->right, key);
}

「三項演算子」 (if-then-else 式) に注意してください?:。

于 2012-05-15T13:58:31.940 に答える
1

検索の再帰呼び出しから実際に結果を返すことはありません。

これらの呼び出しからの戻り値を確認し、ノードが見つかった場合はそれを返す必要があります

data* search(struct data *node, int key)
{
    data* found = NULL;

    if(node == NULL)
        return NULL;

    printf("\n%d %d -", node->number, key);

    if(node->number== key)
        return node;

    found = search(node->left, key);
    if (found)
        return found;

    found = search(node->right, key);
    if (found)
       return found;

    return NULL;
}
于 2012-05-15T14:00:26.587 に答える
1

あなたの戻り値を使用しない限り、検索されたノードは返されませんsearch

このようなものに変更します。

data* search(struct data *node, int key)
{
  if(node == NULL)
    return NULL;
  else
  {
    printf("\n%d %d -", node->number, key);

    if(node->number== key)
        return node;
    struct data *tmp;
    tmp = search(node->left, key);
    /* node found ? */
    if (tmp)
        return tmp;
    tmp = search(node->right, key);
    /* node found ? */
    if (tmp)
        return tmp;
  }
  /* search didn't find anything */
  return NULL;
}
于 2012-05-15T13:59:35.327 に答える
0

二分木を作成するためのはるかに簡単で効率的な方法があり、それは単にベクトル/配列を使用するだけです。

i は、ベクトルにアクセスするための int です。右に行くには、i=i*2 です。左に移動するには、i=i*2+1。それらが同じスポットを共有することは決してなく、各スポットが均等に分配されると仮定します。

于 2012-05-15T14:08:07.317 に答える