Java二叉树插入，不对树进行任何更改

Question

所以我正在努力实现二叉树的插入方法。

据我所知，问题是函数参数中的更改不能正确返回到main（）。

static void addChild(Child c, Child tree){
    if(tree==null){
        tree=c;
    }
    else{
        if(c.cid>tree.cid){
            addChild(c, tree.lc);
        }
        else if(c.cid<tree.cid){
            addChild(c, tree.rc);
        }
    }
}

上面看到的子对象与树中节点的子对象无关。

树节点是子对象。

CID是子类中保存整数的字段。

rc是节点的正确子级。

lc是节点的左子节点。

addChild的参数：

@param Child c：要插入到树中的子级

@param子树：树的根

基本上我的问题是，这不应该正常工作吗？当方法完成时，参数中给出的树的右子级和左子级为null。

Answer 1

您的递归基本情况：

tree = c;

不会更新树。它只是在该调用范围中重新分配树参数的引用。它在特定的递归调用（堆栈帧）之外没有效果。

以下是处决的演练：

Child tree = new Child();
tree.cid = 0;
tree.lc = new Child();
tree.lc.cid = 1;
Child c = new Child();
c.cid = 2;
addChild(c, tree);
    // tree != null
    // c.cid>tree.cid
    addTree(c, tree.lc);
        // tree != null
        // c.cid>tree.cid
        addTree(c, tree.lc);
            // tree == null
            tree = c; // Won't be effective
        return;
    return;

这会局部地改变树引用，并且在这个递归调用之外没有任何影响。

这里的技巧是在这一点上更新父树的左或右子树。

static Child addChild(Child c, Child tree){
    if(tree==null){
        return c;
    }
    else{
        if(c.cid>tree.cid){
            tree.lc = addChild(c, tree.lc);
        }
        else if(c.cid<tree.cid){
            tree.rc = addChild(c, tree.rc);
        }
        return tree;
    }
}

跟踪新版本的过程如下所示：

Child tree = new Child();
tree.cid = 0;
tree.lc = new Child();
tree.lc.cid = 1;
Child c = new Child();
c.cid = 2;
addChild(c, tree);
    // tree != null
    // c.cid>tree.cid
    tree.lc = addTree(c, tree.lc);
        // tree != null
        // c.cid>tree.cid
        tree.lc = addTree(c, tree.lc);
            // tree == null
            return c;
        return tree;
    return tree;

Answer 2

递归方法只修改堆栈上的本地副本。.相反，你应该传递一个指针或传递一个对树节点的引用，这样当你在基本情况下分配一个子节点时，你就可以对实际的父节点而不是本地副本进行更改（本地副本在函数返回后被销毁）