どのようにこの再帰関数をトレースするには？

Question

私は、バイナリ検索ツリーに要素を追加するために、このJava再帰的なプログラムを発見した：それは最後のnを返してから、再度rootにそれを割り当てることがある理由を私は理解していないものを

public void add(int e){ 
    root=add(root, e); 
} 
public Node add(Node n, int e){ 
    if (n==null){ 
     n=new Node(e); 
    } else { 
     if (e<n.elem){ 
      n.left=add(n.left,e); 
     } else{ 
      n.right=add(n.right,e); 
     } 
    } 
    return n; 
} 

です。 助けてください？

Answer 1

割り当ての理由は、Javaには値渡しのパラメータを渡す方法が1つしかないからです。

rootへの参照は、値によってaddに渡されます。ただし、addはルートに渡されたノードを変更する必要があります。たとえば、最初のノードをツリーに追加する場合、rootの値はnullですが、ノードを追加した後はnullになる必要があります。

この制限を回避するイディオムは、変更された値を返すメソッドを作成し、それをパラメータに戻すことです。 if (n==null) n=new Node(e);：それはあなたが再帰を理解したい場合は、あなたのadd方法がここに

root=add(root,e); 

、ここ

n.left = add(n.left, e); 
n.right = add(n.right, e); 

Answer 2

をやっていることで、あなたはそれを終了する条件を見てする必要があります。

これは、Node nがnullの場合に最後のコールが行われることを意味します。いつになりますか？葉の一つに。その後、ツリーに追加される別のオブジェクトが作成されます。その後

、それはreturn nの論理だけです：最後の呼び出しの後、nです：new Node(e)。新しいNodeは誰に割り当てられますか？一部の（元）葉のn.leftまたはn.right。スタック内のメソッドaddへの最初の呼び出しに達するまで、同じロジックがツリーの上に沈みます。それは完全に更新されたツリー、つまりあなたが望む最終製品を返します。