1

ノードの定義は次のとおりです。

struct node{
    int data;
    stuct node * left;
    struct node * right;
};

私がやろうとしているのは、祖先ノードを指すすべてのノードをリストすることです。間違った解決策を投稿し、答えからアドバイスを受けた後、私の新しい解決策は次のとおりです。

二分木を再帰的に調べます。現在のノードをノードの配列に追加してから、現在のノードの子が前の祖先ノードのいずれかを指しているかどうかを確認します。

デフォルトのケースは、ノードがNULLの場合です。その場合、関数は戻ります。

それがどのように機能することになっているのか：

ノードを配列に追加します

左の子がNULLかどうかを確認します。

そうでない場合は、子を前の各ノードと比較します。

障害が見つかった場合は、それを報告します。

そうでない場合は、子を引数として関数を呼び出します。

終了するまで繰り返します。（二分木のrhsについても同じです）

質問：

  • 配列はノードを格納するのに最適ですか？
  • これは機能しますか？for（i = 0; i <sizeof（arrOfNodes）/ sizeof（node）; i ++）
  • 関数は再帰的であるため、配列と配列インデックスは関数内で初期化できません（または初期化できますか？）。グローバルにする必要がありますか？
  • 2つのアレイがある方が良いでしょうか？（1つはLHS用、もう1つはRHS用）

コード：

void findFault(node * root){
    if (root == NULL){
      return;
    }

    arrOfNodes[index++] == root; // array of nodes

    if (root->left != NULL){
      for (i = 0; i < sizeof(arrOfNodes) / sizeof(node); i++){
         if (ar[i] == root->left){
             printf("%d", root->left);
             return;
         }
       }
       findFault(root->left);
    } else return;

    if (root->right != NULL){
      for (i = 0; i < sizeof(ar) / sizeof(node); i++){
         if (ar[i] == root->right){
             printf("%d", root->right);
             return;
         }
      }
      findFault(root->right);
    } else return;
}
4

4 に答える 4

6

再帰についてはわかりませんが、これは次のとおりです。

if (&root->left->left == &root){

私が説明できるより多くの点で間違っていますが、とにかくここに3つの問題があります：

  • なぜrootのアドレスを取得しているのですか？
  • 最初の左ポインタがnullであることをテストしてみませんか？
  • std :: mapを使用することもできますが、バイナリツリーの実装方法を学ぶことも良い考えです。
于 2009-08-23T19:26:25.863 に答える
5

これは、問題に対する不適切な解決策です。ニール・バターワースはすでにあなたのコードに注目していますが、私はアルゴリズムに注目します。

あなたのアルゴリズムは、孫ノードがその祖父母を指しているかどうかという非常に特殊なケースのみをチェックします。あなたがすべきことは、ノードへの道に沿って親を集め、ノードの子がその親の1つではないことを確認することです.

これを行うには多くの方法があります。1 つは、ノード構造体にカウンターを追加し、ツリーの走査を開始する前にすべてのノードのカウンターをゼロに設定することです。ノードに到達するたびに、カウンターがゼロであることを確認してから、カウンターを 1 増やします。これは、カウンターが 0 でない子が表示された場合、既にその子を訪れているため、ツリーが無効であることを意味します。

于 2009-08-23T19:36:17.247 に答える
1

この種のチェックを実行するもう 1 つの方法は、ノードの幅優先スイープを実行する一方で、既にアクセスしたノードのベクトルを保持することです (アドレスでソートしておくことができます)。ノードにアクセスするたびに、それがベクターにないことをアサートし、適切な場所に追加して、アクセスしたリストをソートしたままにします。

この種のチェックの利点は、ツリーまたはノード構造体自体を変更せずに実行できることですが、パフォーマンスが少し低下します。

ノート：

  • 配列は、ノードを格納するための優れた方法です。STL を避けている場合 (興味深い: なぜ?)、自分のメモリを管理する必要があります。実行可能ですが、再発明するのはもろい車輪です。
  • 配列のサイズを取得するための for ループ チェックは機能しません。malloc/free または new/delete を使用する場合は、必要な配列のサイズを事前に指定する必要があります。for ループで毎回計算するのではなく、そのサイズを使用する必要があります。
  • 再帰アルゴリズムの典型的なパターンは、「外部」関数と「内部」関数を持つことです。外側の関数は、外部コードによって呼び出される関数であり、初期設定などを行います。内側の関数は、outser 関数によってのみ呼び出され、より複雑なパラメーター セット (外側の関数によって設定されたデータを取得する) を持つ傾向があり、呼び出します。実際の再帰を実行します。
  • 2 つの配列が必要になります。1 つはアクセスしたノードのリスト用で、もう 1 つはまだアクセスしていないノードのリスト用です。
于 2009-08-23T20:21:26.500 に答える
-1

二分木を生成するアルゴリズムが、ノードの左右の子以外の障害を伝播できるかどうかはわかりません。

とにかく、これはあなたのコードの修正版です：

void findFault(node * root){
    if (root == NULL){
      return;
    }

    if (root->left == root){
      printf("left: %d", root->data);
    } else findFault(root->left);

    if (root->right == root){
      printf("right: %d", root->data);
    } else findFault(root->right);
}
于 2009-08-23T19:44:42.347 に答える