8

再帰関数に関しては、私は絶望的に迷子になっています。二分木をトラバースし、特定の値の間に新しいノードを挿入する再帰関数を作成する必要があります。トラバース関数を再コピーして、それを使用する他のすべての関数で変更する必要がありますか？トラバース機能を評価していただけませんか？

私のトラバースコードは大丈夫だと思います。

Node traverse (Node currentNode){
    if (!currentNode.left.equals(null)){
        traverse (currentNode.left);
        return currentNode.left;
    }
    if (!currentNode.right.equals(null)){
        traverse (currentNode.right);
        return currentNode.right;
    }
    return currentNode;
}
4

3 に答える 3

15

二分木に関しては、再帰的に実行できるトラバーサルにはいくつかの種類があります。それらは、参照されてからアクセスされた順序で書き込まれます（L =左の子、V =そのノードにアクセス、R =右の子）。

  • インオーダートラバーサル（LVR）
  • 逆順走査（RVL）
  • プレオーダートラバーサル（VLR）
  • ポストオーダートラバーサル（LRV）

コードはポストオーダートラバーサルメソッドを実行しているように見えますが、いくつかの問題が混同されています。まず、ノードはトラバースしたいものです。データはあなたが訪問したいものです。次に、これが実装されている方法で、ノード自体を返す理由はありません。あなたのコードでは、「この特定のデータを探しています。Node@ 0xdeadbeefさんがいますか？」という条件を許可していません。これは、ある種の追加の検索パラメーターで見つかります。

アカデミックBSTトラバーサルは、ノード自体のみを出力します。検索機能を追加したい場合は、もう1つのパラメーターと、適切なノードの追加チェックが必要です。

スニペットは次のとおりです。

// Academic

public void traverse (Node root){ // Each child of a tree is a root of its subtree.
    if (root.left != null){
        traverse (root.left);
    }
    System.out.println(root.data);
    if (root.right != null){
        traverse (root.right);
    }
}

// Search with a valid node returned, assuming int

public Node traverse (Node root, int data){ // What data are you looking for again?
    if(root.data == data) {
        return root;
    }
    if (root.left != null && data < root.data) {
        return traverse (root.left, data);
    }
    if (root.right != null && data > root.data) {
        return traverse (root.right, data);
    }
    return null;
}
于 2012-04-12T04:18:13.053 に答える
1

事前注文の方法論を横断しているように見えますが、現在のノードを目的地に到達したことを定義する基本値と実際に比較せずに、正確に何を達成したいかについては少し懐疑的です。簡単なツリーを描き、ステップを視覚化することをお勧めします。次に、それをコードに入れてみてください。

于 2012-04-12T04:06:35.243 に答える
0

再帰関数は、変更されたパラメーターまたは終了（終了）条件を使用してそれ自体の値を返します。例：階乗：

int factorial( int param ) {
   if ( param > 1 ) {
      return param * factorial( param -1 );
   } else {
      return 1;
   }
}

コードでは、「トラバース」を呼び出しますが、結果には何もしません...再帰関数が終了すると、最終的な戻り値は、存在する場合は最初の左の子、存在する場合は最初の右の子、それ以外の場合はルートになります。ノード。

ツリーをトラバースする必要がある理由について詳しく説明してください（また、「関数をコピーして他のすべての関数で変更する」とはどういう意味かわからないので、関数の全体的な考え方は、コードワンスコールメニーです。 ）。

于 2012-04-12T04:03:19.583 に答える