2

二分探索木をたどるプログラムを書いています。コードは次のとおりです。

Main.java

public class Main {

public static void main(String[] args) {
 BinaryTree binaryTree = new BinaryTree();
binaryTree.add(50);
binaryTree.add(40);
binaryTree.add(39);
binaryTree.add(42);
binaryTree.add(41);
binaryTree.add(43);
binaryTree.add(55);
binaryTree.add(65);
binaryTree.add(60);
binaryTree.inOrderTraversal(binaryTree.root);
} 
}

Node.java

 public class Node {
 int data;
 Node left;
 Node right;
 Node parent;


public Node(int d)
{
data = d;
left = null;
right = null;
}
}

BinaryTree.java

public class BinaryTree {
Node root = null;
public void add(int d)
{
Node newNode =  new Node(d);
if(root!=null)
{


    Node futureParent = root;
    while(true)
    {
    if(newNode.data < futureParent.data)      //going left
    {
        if(futureParent.left == null)
        {
            futureParent.left = newNode;
            newNode.parent = futureParent;
            break;
        }
        futureParent = futureParent.left;

    }
    else
    {
        if(futureParent.right == null)
        {
            futureParent.right = newNode;
            newNode.parent = futureParent;
            break;
        }
        futureParent = futureParent.right;
    }

    }

}
else
{
    root = newNode;
}
}
public void inOrderTraversal(Node node)
{
if(node!=null)
{
inOrderTraversal(node.left);
System.out.println(node.data);
inOrderTraversal(node.right);
}
}
}

追加プロセスは完全に理解していますが、トラバーサルを理解するのに苦労しています。今、私が作業しているツリーは、より良い参照のためにこれです:

BinaryTree

関数の最初のステートメントはinOrderTraversal()50,40 にアクセスし、次に 39 にアクセスし、最後に null にヒットして if 条件を false にし、その後 39 が出力され、正しい子が検索されます。この後、最初のステートメントの実行が停止し、2 番目と 3 番目のスタックがアンワインドされます。私が理解していない部分である 40 を印刷して 41 にトラバースするステートメント (inOrderTraversal(node.right)および) につながる、つまり、スタックに新しいものがあるとすぐに実行を停止した後、コンパイラーはどのようにステートメント 1 ( ) を再開しますか。print(node.data)inOrderTraversal(node.left)

4

3 に答える 3

3

古典的な再帰の例である階乗について考えると、再帰とスタックをより明確に理解できます。

int factorial(x) {
   int result;
   if(x==1) 
       result = 1;
   else
       result = x * factorial(x - 1);
   return result;
 }

(result変数を使用して、コードを手動でステップ実行するときに位置をマークしやすくしました)

factorial(5)一枚の紙を使用して、手動での実行を実行します。

「x」を 5 に置き換えて、1 枚の紙に関数を書くことから始めます。次に、それを読み、関数呼び出しに来たら、実行ポイントに鉛筆マークを付けて、新しい紙を用意します。新しい関数呼び出し。

これを行うたびに、新しい紙を前のシートの上に置きます。これは文字通り、紙の束であり、コンピューターの束を正確に表しています。各用紙はスタック エントリであり、作成時にコード内のどこにいたか、およびローカル変数の値が何であったかを記録します。

これは、再帰的な関数呼び出しに限ったことではないことを理解することが重要です。すべての関数呼び出しは、この方法でスタック エントリを作成します。

プログラムの実行では、スタックを参照できません。後入れ先出し(LIFO)の用紙の一番上のシートのみにアクセスできます。に到達するとfactorial(1)、それ自体は再び呼び出されず、 に到達しますreturn。その場合は、一番上の紙を捨てて、戻り値を新しい一番上のレイヤーに書き込んでから、鉛筆の印を付けた場所から一番上のレイヤーの関数をステップ実行します。

このまま続けて、最終的に最後のシートを破棄します。これは、プログラムが終了し、最終結果が得られたことを意味します。

ちなみに、関数が自分自身を呼び出さない場合など、コードに何か問題がある場合は、紙がなくなります (または紙のスタックが天井に達します) 。これがスタック オーバーフローであり、その後、サイト名が付けられています。スタックが課された最大値よりも大きくなり、ランタイムが関数の再呼び出しを拒否します (Java では、例外をスローすることにより)。プログラミングのキャリアの中でこれに遭遇する可能性があります。一般的な原因は、不適切にコーディングされた停止条件、または循環データ構造をぐるぐる回っていることです。

上記の実装でfactorial(0)は、おそらくスタック オーバーフローが発生します。理由がわかりますか？

これが、従来のすべてのコンピューター プログラムの実行方法です。スタックに 1 つのアイテムを配置します (C および Java では、それは ですmain())。関数呼び出しが行われるたびにスタックが大きくなり、関数が完了するたびにスタックが縮小します。スタックは、最終的に何もなくなるまで拡大および縮小し、その時点でプログラムは完了します。

あなたのようなプログラムの場合、同じ関数で 2 つの再帰呼び出しを使用しても、何も違いはありません。動作を確認するために行ったのと同じ方法で、紙を使って小さな二分木検索を手動で実行することは良い練習になりますfactorial()。

また、デバッガーで Java コードを一時停止して現在のスタックの状態を確認することも有益です。それができない場合は (デバッガーの使用方法をすぐに学習してThread.dumpStack()ください)、コードのどこかに を挿入して出力を確認します。 .

于 2014-02-27T09:05:17.320 に答える
1

あなたのコードはそのままでは機能しません。ノード 39 を永遠に繰り返します。メソッド inOrderTraversal() は確かに左側のノードに移動しますが、while のために永久に循環します。各スタック フレームには、変数の独自のコピーがあります。メソッドに入ると、変数 node は引数として渡されたオブジェクト参照のコピーを取得します。

再帰について考える 1 つの方法は、while ループの使用に似ていますが、while の代わりに if があります。メソッドは次のようになります。

    public void inOrderTraversal(Node node) {
    if (node != null) {
        inOrderTraversal(node.left);
        System.out.println(node.data);
        inOrderTraversal(node.right);
    }
}

ツリーをトラバースするとき、一番左のノードに格納されている小さい値を最初に出力する必要があるinOrderTraversal(node.left);ため、if を取得するために使用します。null ノードに到達すると、これはその親が一番左のノードであることを意味するため、それを出力します。その後、適切なノードに移動してプロセスを繰り返します。これは、ツリーを分割できなくなるまでツリーを小さなサブツリーに分割し、その値を出力するようなものです。

メソッドを (再帰的かどうかに関係なく) 呼び出すたびに、新しいスタック フレームが割り当てられ (スタックにプッシュされ)、メソッドの終了後にスタックが削除され (ポップされ)、ガベージ コレクション用のスペースが解放されます。これらのスタック フレームは、ローカル変数が存在する一時的なスペースにすぎません。オブジェクトのメンバー変数は、スタックよりも長い寿命を持つヒープと呼ばれる別の場所に存在します。

JVM はこれらのスペースの割り当てを処理し、ガベージ コレクターはオブジェクト/変数の寿命に応じてスペースを解放します。彼らがどれだけ住んでいるかに応じて、いくつかの世代があります（それは彼らが呼ばれるものです）。すべては eden (若い) 世代から始まり、ガベージ コレクターがまだ生きているためにスペースを再利用しない場合は、生存世代に移動され、その後、まだ収集されていない場合は、最後の世代に移動します。 、在職世代。オブジェクトの存続期間が長ければ長いほど、GC によってチェックされる頻度は低くなります。これは、エデン内のオブジェクトが非常に高速に収集される一方で、残りの世代がそれほど頻繁にチェックされないことを意味します。パーマネント ジェネレーション (permgen) と呼ばれる別のスペースもあり、定数が (文字列リテラルのように) 存在し、クラスが格納されます。

于 2014-02-27T08:15:58.477 に答える
0

まず、中のwhile記述inOrderTraversalが間違っています。whileループ内のどのステートメントも変数を変更しnodeないため、変更された場合nullは常に変更され、変更されていない場合は変更されません。に変更しifます。

そのため、再帰を調べる方法は、多くの場合帰納法です。私は次の帰納仮説を主張します。

Tをルートとするツリーを指定すると、 の順序どおりのトラバーサルが出力されnode、返されます。inOrderTraversal(node)T

これが実際に起こることを帰納法によって示すことができます。単純なケースは whennode == nullです。その場合、inOrderTraversal何も出力せずに直接返します。これは仮説と一致しています。

ここで、空でないツリーを渡すとします。帰納法によりinOrderTraversal(node.left)、左のサブツリーを出力して戻ります。次に、node.data印刷されます。最後に、再び帰納法によりinOrderTraversal(node.right)、正しいサブツリーを出力して戻ります。これまでのところ、現在のツリーは順番にトラバーサルされていることに注意してください。をメソッドの戻り値に変更したwhileため、誘導仮説が満たされました。if

これはあなたの質問に答えていますか？

于 2014-02-27T07:54:54.927 に答える