java - 使用递归返回的对树中节点的引用不允许更改节点本身

Question

我的数据结构类(class)正在处理树。我们正在实现一个三叉树，包含 2 个值，并引用左、中、右节点(左子树小于值 1，中间子树位于值 1 和值 2 之间，右子树大于值 2 )。 Tree类已经提供了接口(interface)，查找、插入、删除方法必须是递归的。将对其进行测试的客户端代码重复使用插入方法来创建树，并且根从 null 开始。

我试图通过在单独的私有(private)方法中查找父节点，然后根据需要更改返回的节点，以递归方式将值插入到树中。当前的问题是该方法返回初始节点(即根)，并正确创建具有该值的新节点，因为根为空。但是，根仍然为空。

我非常确定这是由于 Java 中引用和值的工作方式造成的(类似于 this article by Jon Skeet 中描述的 C#)；考虑到限制，我应该如何更改它以允许插入到树中？下面是树类中当前的 insert 方法，以及类似的私有(private)方法。

public void insert(AnyType newData)
{
    // If insert node is null, make a new node with newData as first key
    TernaryNode<AnyType> insert_node = findNode(newData, root);
    if (insert_node == null)
    {
        insert_node = new TernaryNode<AnyType>(newData);
    }
    else
    {
        // Get the key that is equal if the insert node is not null
        if (insert_node.getKey1() == null)
        {
            insert_node.setKey1(newData);
        }
        else
        {
            insert_node.setKey2(newData);
        }
    }// end else
}// end insert

private TernaryNode<AnyType> findNode(AnyType item, TernaryNode<AnyType> node)
{
    TernaryNode<AnyType> current_node = node;
    if (current_node != null)
    {
        if (current_node.getKey1() != item &&
                current_node.getKey2() != item)
        {
            // Comparator checks left
            if (compare.compare(current_node.getKey1(), item) <= -1)
            {
                return findNode(item, current_node.left);
            } // Comparator checks right
            else  if (compare.compare(current_node.getKey2(), item) >= 1)
            {
                return findNode(item, current_node.right);
            }// Comparator checks middle
            else
            {
                return findNode(item, current_node.middle);
            }
        }// end while
    }// end if
    // Return current node even if it is null
    return current_node;
}// end findNode

Answer 1

除非您将某些内容分配给 root 成员，否则它永远不会获取值。您的树可能需要某种外部容器，类似于 XML 文档(也是一棵树)具有与实际文档根节点不同的外部 Document 对象。