java - 如何跟踪这个递归函数？

Question

我找到了这个用于将元素添加到二叉搜索树中的 Java 递归程序:

public void add(int e){
    root=add(root, e);
}
public Node add(Node n, int e){
    if (n==null){
        n=new Node(e);
    } else {
        if (e<n.elem){
            n.left=add(n.left,e);
        } else{
            n.right=add(n.right,e);
        }
    }
    return n;
}

我不明白的是为什么最后要返回n，然后再赋值给root。

Answer 1

赋值的原因是Java只有一种传递参数的方法——传值。

对 root 的引用按值传递给 add 方法。但是，add 需要修改作为根传递给它的节点:例如，当您将第一个节点添加到树中时，root 的值为 null，但需要添加节点后变为非null。

解决此限制的习惯用法是创建一个返回修改后的值的方法，并将其分配回参数。这就是您的 add 方法在这里所做的

root=add(root,e);

这里

n.left = add(n.left, e);
n.right = add(n.right, e);