Структура данных дерева addnode

Question

У меня возникла проблема с пониманием следующего кода. Это структура данных дерева, и я не понимаю, зачем нам нужен два узла (родительский и focusnode) в методе addnode(). Я попытался сделать это только с focusnode, но это не сработает. Моя идея установлена ​​в focusnode на корню, и продолжайте ее зацикливание до тех пор, пока 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

Потому что, если вам нужно назначить новый узел как parent «s .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 материнство.right or parent.left`.

Таким образом, вы будете установить focusnode ссылку на ваш newnode, но .left/.right дочерние узлы родительского не будут ссылаться на ваш newnode.

Если вы исходите из C/C++ или аналогичного, представьте, что все эти переменные являются указателями. *focusnode указывает на тот же объект, на который указывает *parent.left. Создание *focusnode указывает на другой объект, который не изменит то, что указывает *parent.left.

Все переменные в Java являются ссылками (помимо примитивов типа int/double и т. Д.), Которые аналогичны указателям на C/C++.

Answer 2

Если вы делаете чек, как это:

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

Вы зацикливание до focusnode не равна нулю, то создание нового узла, но не закрепив его на родительский узел. В результате, когда вы пытаетесь снова зацикливаться, вы не можете пройти мимо корневого узла, так как у него нет детей! Если вы хотите избежать использования переменной родительского узла, вам нужно проверить дочерний элемент в состоянии перед установкой focusnode и установить set focus, если дочерний элемент не равен нулю. например:

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

Проверка одинаковая для правой стороны.