Baum Datenstruktur Addnode

Question

Ich habe Probleme mit dem folgenden Code zu verstehen. Es ist eine Struktur Baumstruktur und ich verstehe nicht, warum brauchen wir zwei Knoten (Eltern und focusnode) in der addnode() Methode. Ich habe versucht, es mit nur focusnode zu tun, aber es funktioniert nicht. Meine Idee ist zu root, und halten Sie es in Schleife, bis ist gleich null, und setzen Sie focusnode auf 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

Denn wenn Sie einen neuen Knoten als parent ‚s .left oder .right Kind zuweisen müssen (was nach dem Fall feststellen, dass focusnode == null ... was bedeutet, .left/.right null ist), dann müssen Sie einen Verweis auf das .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`.

So finden Sie den focusnode Bezug auf Ihre newnode gesetzt, aber die .left/.right Kindknoten des Elternteils wird Ihre newnode nicht verweisen.

Wenn Sie aus C/C++ oder ähnlichem kommen, stellen Sie sich vor, dass alle diese Variablen Zeiger sind. *focusnode zeigt auf das gleiche Objekt, auf das *parent.left zeigt. Wenn Sie *focusnode auf ein anderes Objekt zeigen, ändert sich nichts, was auf *parent.left zeigt.

Alle Variablen in Java sind Referenzen (abgesehen von Primitiven wie int/double usw.), die den Zeigern in C/C++ ähnlich sind.

Answer 2

Wenn Sie das Kontroll wie dies tun:

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

Du Looping bis focusnode null ist, dann einen neuen Knoten zu schaffen, aber nicht an der den übergeordneten Knoten anzubringen. Wenn Sie also versuchen, eine Schleife erneut zu erstellen, können Sie nicht mehr an dem Stammknoten vorbeilaufen, da er keine untergeordneten Elemente enthält. Wenn Sie vermeiden möchten, mit der übergeordneten Knotenvariablen umzugehen, müssen Sie das Kind in der Bedingung überprüfen, bevor Sie den Fokusknoten setzen, und nur den Fokusknoten setzen, wenn das Kind nicht null ist. Beispiel:

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

Die Überprüfung ist für die rechte Seite gleich.