为什么在这个二进制树的方法insert方法中，root始终为null

我试图为BST类实现一个递归插入节点方法

public void insertNode(Node r, Node n) { if(r == null) { System.out.println("r=n"+ n.data); r = n; } else { System.out.println("r=! null finding place in tree for "+ n.data); if(n.data <= r.data) { if(r.left == null) r.left = n; else insertNode(r.left, n); } else { if(r.right == null) r.right = n; else insertNode(r.right, n); } } } 

我试图像这样调用这个方法：

  int[] arrTree = {34, 2, 56, 12, 44, 39, 56, 1}; BT t = new BT(); for (int i = 0; i < arrTree.length; i++) { //System.out.println("Tree Root = "+ t.getRoot()); BT.Node n = t.new Node(arrTree[i]); t.insertNode(t.root, n); } 

但我总是得到这个输出：

  r=n34 r=n2 r=n56 r=n12 r=n44 r=n39 r=n56 r=n1 

Node是BT的内部类。

经过几个小时的跑步和尝试不同的事情，我无法弄清楚我做错了什么。

Answer 1

根据您显示的代码判断，我的钱是错误的：

 public void insertNode(Node r, Node n) { if(r == null) { System.out.println("r=n"+ n.data); r = n; //you overwrite the value of r but never use it } 

Node r实际上是对t.root引用的任何t.root的单独引用，因此将r替换为另一个值将不会改变t.root指向方法之外的任何t.root 。 您可以修改方法内的引用数据，但不能修改引用本身。

Answer 2

Java是pass-by值语言。 如果是对象，则传递引用的值，从而创建新引用 。

 public void insertNode(Node r, Node n) { if(r == null) { r = n; } 

在这里，您将新引用替换为另一个引用的根; 原始引用root（ t.root ）保持不变。

要解决此问题，您可以删除insertNode()方法中的第一个参数 – 树的根是其实现的一部分，因此树已经知道对其根的引用。 将insertNode()所有内容更改为this.root 。

Answer 3

在方法中设置r时，它不会影响您传入的节点。因此永远不会设置t.root。