1

我刚刚了解了二叉树，并尝试创建一个插入方法。我的第一种方法不起作用，我做了一些调整。它现在有效，但我不明白为什么以前的方法失败了。

不起作用的方法是：

if(root == null)
    {
        root = new Node(data);
    }
    else if(data < root.getData())
    {
        insertNode(root.getLeft(), data);
    }
    else
    {
        insertNode(root.getRight(), data);
    }

有效的方法是：

    if(data < root.getData())
    {
         if(root.getLeft() == null)
         {
             root.left = new Node(data);
         }
         else
         {
             insertNode(root.getLeft(), data);
         }
     }

     else
     {
         if(root.getRight() == null)
         {
             root.right = new Node(data);
         }
         else
         {
            insertNode(root.getRight(), data);
         }
     }

关于为什么会这样的任何解释？因为在我看来，root 应该等于 root.left，所以将 root 设置为新节点应该与将 root.left/right 设置为新节点相同。

4

2 回答 2

2

在您的第一个方法中，您将 null 输入到您的 insertNode 方法中，但没有引用指针。因此，您在 insertNode 方法中设置了 root = new Node()，但父节点对此一无所知，它仍然指向 null。

由于这是一些非常基本的 Java 理解，我建议阅读一些关于“java 参数传递”的文章，例如http://javadude.com/articles/passbyvalue.htm

于 2013-09-25T08:24:23.963 回答
0

假设您递归调用该方法insertNode(root, data)，您必须确保它root不是null，这意味着执行root = new Node(data);会创建一个可见性仅限于insertNode方法的对象。

如果不是，您可以重写insertNode(data)为非递归并root在它内部创建如果它是null.

public void insert(int data) {
    if(root == null){
        root = new Node(data);
    }
    else {
        Node current = root;
        Node previous;
        String from;
        while(current != null) {
            previous = current;
            if(data < current.getData()) {
                current = current.left();
                from = "left";
            }
            else {
                current = current.right();
                from = "right";
            }
        }
        current = new Node(data);
        if(from.equals("left")) {
            previous.left() = current;
        } else {
            previous.right() = current;
        }
    }
}
于 2013-09-25T08:30:14.183 回答