树数据结构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

回答

相关问题