Параметр Java, проходящий в bst implementationaion

Question

Я возвращаюсь на Java после долгого времени с помощью C и был пойман на простой концепции. Я начал писать базовую реализацию BST, чтобы вернуть свои данные, и подумал, что я понимаю передачу параметров передачи по значению Java (да, я понимаю, что даже ссылки на объекты передаются по значению, очень распространенное недоразумение).

Я реализую функцию добавления рекурсивно, как показано в приведенном ниже коде, однако я обнаружил, что, если я фактически не вернул значения узлов, это не сработает. Я прокомментировал строки, которые не работают, и заменил их линиями, которые работают для сравнения.

Я думал, что, поскольку копия ссылки на фактический корневой узел передается функции добавления, изменения, выполняемые в каждом вызове функции, выполняются на фактическом объекте в памяти, поэтому, если я добавил узел влево или вправо, его следует сохранить.

Я чувствую себя очень смущенным, потому что знаю, что мне, должно быть, не хватает чего-то действительно простого здесь, но чтение о передаче java-аргументации заставляет меня задаться вопросом, почему я ошибаюсь. Спасибо за помощь.

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

Это потому, что в вашем методе void add, вы устанавливаете корень, равный результату TreeNode add, так что вы должны вернуть что-то или другое корень будет нулевым. Например, давайте добавим первый элемент в BST. После запуска метода TreeNode add что-то нужно вернуть, потому что в конечном итоге оно будет назначено root в вашем методе void add. Вот краткое изложение того, что произойдет, если вы ничего не вернете.

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 

Вы думаете, что корень на самом деле меняется на новый объект TreeNode с его значением элемента в 10. Тем не менее, этого не происходит. Скорее всякий раз, когда вызывается метод, который принимает параметры, указываются указатели, указывающие на объекты в этих параметрах. Поэтому при вызове TreeNode add(root, 10) создается указатель на root. Этот указатель называется node, поэтому, когда вы меняете node в последней строке здесь, он меняет то, на что указывает указатель node, оставляя root нетронутым. Если вы не вернетесь node, то вы ничего не делаете с этой ссылкой на новый объект TreeNode, который вы только что создали, чтобы он потерялся в сборке мусора Java.