ツリーデータ構造addnode

Question

次のコードを理解する上で問題があります。それはツリーのデータ構造であり、addnode()メソッドで2つのノード（親とfocusnode）が必要な理由はわかりません。私はちょうどfocusnodeでそれをやろうとしましたが、うまくいきません。私の考えはfocusnodeをrootに設定し、focusnodeがnullに等しくなるまでループし続け、focusnodeをnewnodeに設定します。

public class tree { 
    node root; 
public class node{ 

    private int key; 
    private node left; 
    private node right; 

    node(int key){ 
     this.key = key;  
} 

    public int getkey(){ 
     return key; 
    } 

    public node getleft(){ 
     return left; 
    } 

    public node getright(){ 
     return right; 
    } 

} 

public void addnode(int key){ 
    node newnode = new node(key); 
    if(root == null){ 
     root = newnode; 
    }else{ 
     node focusnode = root; 
     node parent; 

     while(true){ 

      parent = focusnode; 
      if(key < focusnode.key){ 
       focusnode = focusnode.left; 

       if(focusnode == null){ 
        parent.left = newnode; 
        return; 
       } 
      }else{ 
       focusnode = focusnode.right; 

       if(focusnode == null){ 
        parent.right = newnode; 
        return; 
       } 


     } 
     } 
    } 
} 
public void runnode(node focusnode){ 
    if(focusnode != null){ 
     runnode(focusnode.left);   

    runnode(focusnode.right); 
    System.out.println(focusnode.key); 
    } 

}` 

Answer 1

あなたは（あなたが意味focusnode == null ... .left/.rightがnullであることを見つけるの後に起こる）parentの.leftまたは.right子として新しいノードを割り当てる必要がある場合、あなたはそれへの参照を必要とするので.left/.right child (the reference is from the parent). You can't set focusnode to your newnode, because it will only assign your newnode to focusnode and not to parent.right or parent.left`。

つまり、あなたのnewnodeへfocusnodeの参照を設定しますが、親の.left/.right子ノードは、あなたのnewnodeを参照しません。

C/C++などから来ている場合は、これらの変数がすべてポインタであるとします。 *focusnodeは、*parent.leftが指しているのと同じオブジェクトを指しています。 *focusnodeを別のオブジェクトに設定しても、*parent.leftが指しているものは変更されません。

Javaのすべての変数は、C/C++のポインタに似ている（int/doubleなどのプリミティブとは別に）参照です。

Answer 2

あなたは、このようなチェックを行っている場合：

if(key < focusnode.key){ 
    focusnode = focusnode.left; 
     if(focusnode == null){ 
      focusnode = newnode; 
      return; 
     } 
    } 
} 

あなたはfocusnodeがnullになるまで、新しいノードを作成し、ループが、親ノードに取り付けるされていません。その結果、ループを再試行しようとすると、子ノードがないため、ルートノードをループすることはできません。親ノードの変数を扱わないようにするには、focusnodeを設定する前の状態で子をチェックし、子がnullでない場合にのみfocusnodeを設定する必要があります。例：

if(key < focusnode.key){ 
     if(focusnode.left == null){ 
      focusnode.left = newnode; 
      return; 
     } else { 
      foucusnode = focusnode.left; 
     } 
    } 
} 

右側のチェックも同じです。