0

我的数据结构类正在使用树。我们正在实现一个 3 叉树，包含 2 个值并引用左、中和右节点（左子树小于值 1，中间子树在值 1 和值 2 之间，右子树大于值 2 ）。为 Tree 类提供了接口，find、insert 和 delete 方法必须是递归的。将对其进行测试的客户端代码重复使用 insert 方法来创建树，并且根以null.

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

我很确定这是由于引用和值在 Java 中的工作方式（类似于Jon Skeet 在这篇文章中描述的 C# ）；考虑到约束，我应该如何改变它以允许插入树？下面是树类中的当前插入方法，以及类似的私有方法。

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
4

2 回答 2

1

除非您为root成员分配某些东西，否则它永远不会获得价值。您的树可能需要某种外部容器，类似于 XML 文档（也是树）有一个Document与实际文档根节点不同的外部对象。

于 2009-11-26T22:23:08.323 回答
0 
    TernaryNode<AnyType> insert_node = findNode(newData, root);
    if (insert_node == null)
    {
            insert_node = new TernaryNode<AnyType>(newData);
            root = insert_node;
    }
于 2009-11-26T22:40:43.447 回答