3 
public static void preorder(Node root) {
    if(root == null) return;

    root.printValue();
    preorder(root.getLeft());
    preorder(root.getRight());
}

私はこの関数を何度も実行しようとしましたが、左のすべての子をトラバースした後、アルゴリズムが最も近い先祖 (親) に戻る方法をまだ理解できません。誰かが私にこれを説明してくれませんか。

4

2 に答える 2

8

returnメソッドの最後に暗黙がありますvoid：

public static void preorder(Node root) {
    if(root == null) return;

    root.printValue();
    preorder(root.getLeft());
    preorder(root.getRight());
    return;
}

呼び出し元のメソッドに常に戻ります。したがって、親のメソッド呼び出しが子に対して別の呼び出しを行う場合、子のメソッド呼び出しが戻ると、親のメソッド呼び出しに戻ります。右？

それが理にかなっていることを願っています。コンが言ったように、紙の上でアルゴリズムを実行するだけです。または、デバッガーの使用方法を知っている場合は、デバッガーでコードをステップ実行して、それがどのように機能するかを確認できます。

于 2013-09-13T05:07:08.597 に答える
2

トラバーサルがリーフ ノードに到達すると、左右の子は NULL になります。preorder(root.getLeft()) は NULL を渡して戻ります。同様に、右も NULL を返します。次に、スタックがポップされ、親に戻ります。

スタックを使用してこれを予行演習できれば、よりよく理解できるようになると思います。

于 2013-09-13T05:10:20.307 に答える