2 
typedef struct dt {
    .....;
} Data;

typedef struct nd {
    int id;
    Data *data;
    struct tm *_parent;
    struct tm *_child[7];
} Node; 


Node* findNode(int id, Node *tree) {
    Node *p = tree;
    if (id == p->_id)
        return p;
    for (int i = 0; i < 7; i++) {
        if (id == p->_child[i]->_id) {
            p = p->_child[i];
            break;
        } else if(p->_child[i] != NULL) {
            findNode(id, p->_child[i]);
        }
    }

    return p;
}

すべてのノードが 0 ～ 7 の子で構成される多方向ツリーがあります。子は順不同で追加および削除できます。指定された ID がツリーを検索し、特定のノードへのポインターを返す検索アルゴリズムを構築しようとしています。上記のように再帰的に実行しようとしましたが、あまり運がありませんでした。このアルゴリズムを再帰的に構築することは実際に可能ですか、それともスタックを使用する必要がありますか?

4

2 に答える 2

1

このアルゴリズムを再帰的に構築することは実際に可能ですか?

はい、再帰を使用してこれを行うことは可能です。

あなたは正しい軌道に乗っています。コードにはいくつかの修正が必要です。

  1. の最初の部分はif (id == p->_child[i]->_id)...、再帰呼び出しがとにかく行うことを複製するため、完全に冗長です (そして、子が であるかどうかを確認できませんNULL)。
  2. 関数が自分自身を再帰的に呼び出す場合、戻り値は無視されます。その戻り値をどうするかを理解する必要があります。
于 2012-11-23T14:11:28.083 に答える
0

終了条件に問題があります。ループで ID が見つからない場合は、戻り値から検出できる必要があります。その場合は NULL にするのが賢明です。これは、2 つの変更を行うことで実行できます。p を設定して break を実行する代わりに、それを直接返し (この方法では、id が見つからない場合にのみ for ループが終了します)、最後の return p を return NULL に変更します。

次に、再帰呼び出しを行うときに、戻り値を確認する必要があります。NULL の場合は続行します。それ以外の場合は返却してください。

そして、特にNULLをチェックする必要がある（しかしチェックしない）ため、子IDのチェックも削除する方がよいという前の回答は正しいです。

于 2012-11-23T14:12:48.647 に答える