樹數據結構addnode

我在理解下面的代碼時遇到問題。這是一個樹形數據結構，我不明白爲什麼我們需要兩個節點（父節點和focusnode）在addnode()方法中。我試圖用focusnode這樣做，但它不起作用。我的想法是設置focusnode爲根，並保持循環，直到focusnode等於null，並將focusnode設置爲newnode。樹數據結構addnode

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); 
    } 

}`

來源

2016-08-03 user3725988

因爲如果你需要分配一個新的節點作爲parent的.left或.right子（發生後，你會發現focusnode == null ...這意味着.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`。

所以你的focusnode基準設置爲您newnode，但父母的.left/.right子節點不會引用您的newnode。

如果你來自C/C++或類似的，想象所有這些變量都是指針。 *focusnode指向*parent.left指向的同一對象。製作*focusnode指向不同的對象不會改變*parent.left指向的內容。

Java中的所有變量都是引用（除了像int/double等基本類型），它們與C/C++中的指針類似。

來源

2016-08-03 01:53:42

難道我們不能擺脫父母，並使用focusnode作爲參考？ – user3725988

'focusnode'指向'.left' /'.right'節點。如果將'newnode'分配給'focusnode'，那麼'focusnode'將不再引用'.left' /'.right'（當前爲'null'），而是引用您的'newnode'。但是如果我們記得'parent'，那麼我們可以說'parent.left'並且改變了父節點的引用，即.left' /'.right'，這就是樹結構所依賴的。分配給'focusnode'不會改變'parent.left'引用的內容。 –

如果你正在做的檢查是這樣的：

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

你循環，直到focusnode爲空，然後創建一個新的節點，但它不附加到父節點。因此，當您嘗試再次循環時，由於它沒有子節點，因此無法循環通過根節點！如果您希望避免處理父節點變量，則需要在設置focusnode之前在條件中檢查子項，並且如果子項不爲null，則只需設置focusnode。例如：

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

該檢查對於右側是相同的。

來源

2016-08-03 02:01:48 naffarn

樹數據結構addnode

回答

相關問題