Java-Parameter übergeben in bst Implementierung

Question

Ich bin nach einer langen Zeit mit C nach Java zurückgekehrt und bin auf einem einfachen Konzept gefangen worden. Ich fing an, eine grundlegende BST-Implementierung zu schreiben, um mich zu orientieren, und dachte, ich würde Javas Pass-by-Value-Parameterübergabe verstehen (ja, ich verstehe, dass sogar Objektreferenzen wertmäßig weitergegeben werden, ein sehr häufiges Missverständnis).

Ich implementiere die Add-Funktionalität rekursiv wie im folgenden Code gezeigt, aber ich fand, dass, wenn ich nicht wirklich die Knotenwerte zurückgeben, es nicht funktioniert. Ich habe die Zeilen, die nicht funktionieren, auskommentiert und sie durch die Zeilen ersetzt, die zum Vergleich dienen.

Mein Gedanke war, dass, weil eine Kopie des Verweises auf den tatsächlichen Wurzelknoten an die Add-Funktion übergeben wird, die Änderungen in jedem Funktionsaufruf auf dem tatsächlichen Objekt im Speicher getan werden, also wenn ich einen Knoten hinzugefügt habe zum linken oder rechten Zweig sollte es beibehalten werden.

Ich fühle mich sehr beschämt, weil ich weiß, dass ich etwas wirklich einfaches hier vermissen muss, aber das Lesen über Java-Argument, das vorübergeht, lässt mich mich wundern, warum ich mich irre. Danke für die Hilfe.

public class BinaryTree { 

    TreeNode root; 

    public BinaryTree(){ 
     root = null; 
    } 

    void add(int item){ 
     root = add(root,item); 
     //add(root,item); 
    } 

    //public void TreeNode add(TreeNode node, int item){ 
    public TreeNode add(TreeNode node, int item){ 
     if(node == null){ 
      node = new TreeNode(item); 
     } else if(item <= node.getItem()){ 
      node.setLeft(add(node.getLeft(),item)); 
      //add(node.getLeft(),item); 
     } else if(item > node.getItem()){ 
      node.setRight(add(node.getRight(),item)); 
      //add(node.getRight(),item); 
     } 
     return node; 
     //return; 
    } 
    static void printTree(BinaryTree tree){ 
     printTree(tree.root); 
    } 
    static void printTree(TreeNode node){ 
     if(node == null){ 
      System.out.println("Tree Empty"); 
      return; 
     } 
     if(node.getLeft() != null) 
      printTree(node.getLeft()); 
     if(node.getRight() != null){ 
      System.out.print(node.getItem()+ ", "); 
      printTree(node.getRight()); 
     } else { 
      System.out.print(node.getItem()+ ", "); 
     } 
     return; 

    } 

    public static void main(String args[]){ 
     BinaryTree tree1 = new BinaryTree(); 
     tree1.add(10); 
     tree1.add(3); 
     tree1.add(5); 
     printTree(tree1); 
    } 
}` 

Answer 1

Es ist, weil in Ihrer void add Methode, Sie sind die Wurzel gleich das Ergebnis der TreeNode add Einstellung, so dass Sie etwas oder auch die Wurzel zurückkehren werden null sein. Zum Beispiel fügen wir das erste Element zur BST hinzu. Nach dem Ausführen der TreeNode add-Methode muss etwas zurückgegeben werden, da dies schließlich root in Ihrer void add-Methode zugewiesen wird. Hier ist ein Überblick darüber, was passieren wird, wenn Sie nichts zurückgeben.

void add(10) gets executed 
root = add(root, 10) 
TreeNode add(root, 10) gets executed 
if(node == null) evaluates to true 
node = new TreeNode(10); // this is where java being pass by value matters 

Denken Sie, dass root tatsächlich mit seinen Elementwert als 10 zu einem neuen TreeNode Objekt verändert sich, dies geschieht nicht. Immer wenn eine Methode aufgerufen wird, die Parameter akzeptiert, werden Zeiger erzeugt, die auf die Objekte in diesen Parametern zeigen. Wenn Sie also TreeNode add(root, 10) aufrufen, wird ein Zeiger auf root erstellt. Dieser Zeiger wird node genannt. Wenn Sie also in der letzten Zeile hier node ändern, ändert sich der Wert des Zeigers node, so dass root unverändert bleibt. Wenn Sie node nicht zurückgeben, tun Sie nichts mit diesem Verweis auf das neue TreeNode-Objekt, das Sie gerade erstellt haben, sodass es in der Garbage Collection von Java verloren geht.