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);
        }
    }
}

上面看到的Childobjects与树中节点的children无关

树节点是Child objects。

cid 是 Child class 中的一个字段，它包含一个整数。

rc是一个节点的右边child。

lc 是节点的左边child。

add 的参数Child:

@param Child c : Child 插入树

@param Child tree : 树的根

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

Answer 1

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

Answer 2

您的递归基本情况：

tree = c;

不会更新树。它只是在该调用范围内重新分配 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
    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;

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

Java binary tree insert not making any changes to the tree

java

tree

binary-tree