0

编辑：正确的解决方案：

void add(Student s)
{
    if(root == null)
        root = new TreeNode(s);
    else
        insert(root,s);        
}

void insert(TreeNode tn, Student s)
{
    if(tn.sVal.compareTo(s) > 0)
    {
        if(tn.left != null)
            insert(tn.left, s);            
        else
        {
            tn.left = new TreeNode(s);
            tn.left.parent = tn;
        }
    }
    else if(tn.sVal.compareTo(s) < 0)
    {
        if(tn.right != null)
            insert(tn.right, s);
        else
        {
            tn.right = new TreeNode(s);
            tn.right.parent = tn;
        }
    }
    balance(tn);
}

我正在尝试使用以下内容插入二叉树：

void add(Student s)
    {
        insert(root,s);
    }

private void insert(TreeNode t, Student s)
{        
    if(t == null)
        t = new TreeNode(s);        
    else if(t.sVal.compareTo(s) > 0)
        insert(t.right, s);
    else if(t.sVal.compareTo(s) < 0)
        insert(t.left,s);                
}

但是，树仍然是空的，我不知道为什么。我讨厌如此含糊，但我在逻辑中找不到错误。我错过了什么？

4

3 回答 3

3

这是一个重要提示：首先进行此更改，然后从那里进行调试：

if (t == null)
    throw new IllegalArgumentException();

还有一个更大的提示：当您创建新节点时，您还必须引用其父节点，以便将其添加到父节点。

于 2012-04-10T20:32:06.340 回答
2

您的代码显示出对 Java 的基本误解，我将尝试帮助您了解哪里出错了。

当您调用 时insert(root,s)，您传递的是对指向的同一 TreeNode对象的引用。然后，当您在函数内部分配时，您将新的引用分配给，而不是。roott = new TreeNode(s)inserttroot

Java 是按值传递的，在对象的情况下，这意味着它正在传递引用的值。如果你知道 C，你可以把它想象成一个指针。它是传递内存地址，而不是传递指向内存地址的指针。

于 2012-04-10T20:27:37.310 回答
0

It's a pointer issue. When you redefine pointer a using the = operator, all previous references to a are lost. In order to keep these references, you either have to change the object using member functions (class methods in Java) or write code to directly fix the references.

Put simply, redefining a pointer affects only that pointer. Anything which already references the pointer will not be updated.

Pseudocode Example:

Node a = new Node("hello")
Node b = a
a = new Node("goodbye")

print(a) // this prints "goodbye"
print(b) // this prints "hello"

In order for b to point to the new a, you must write b = a.

Having sorted that out, you will need to rewrite your insert() method. Because a tree is recursive, a recursive insert() method should do the trick. There are a variety of resources online for recursive tree implementations if you need them: Recursive Tree Java

于 2012-04-10T20:53:52.133 回答