插入BST而不使用头节点JAVA

Question

我正在为BST开发一个递归插入方法。假定该函数是一个递归辅助方法，并且位于名为Node的私有类中。节点类位于名为BinarySearchTree的类中，该类包含根的实例变量。当我尝试插入一个元素时，我在以下位置得到一个NullPointerException：

这左=插入（（节点）左）。元素）；

我不确定为什么会发生这种情况。如果我理解正确，在BST中，我假设将项目插入到所横穿路径的最后一点。感谢您的帮助！

private class Node implements BinaryNode<E>
{
    E item;
    BinaryNode<E> left, right;

   public BinaryNode<E> insert(E item)
   {
       int compare = item.compareTo(((Node)root).item);

       if(root == null)
       {
           root = new Node();
           ((Node)root).item = item;
       }
       else if(compare < 0)
       {
           this.left = insert(((Node)left).item);
       }
       else if(compare > 0)
       {
           this.right = insert(((Node)right).item);
       }

        return root;
     }
}

Answer 1

这是因为在成功插入之前，您正在从空对象读取参数。另外，你的左和右都是空的，所以我将留给你去弄清楚，但是想想看。您应该插入新节点（项目）。如果您的函数是递归的，那么您需要传入当前parentNode（root）的引用。下面是一个框架，希望您能够理解代码。

   private Node<Item> insert(Node traversedNode, Item item)
   {
     if(traversedNode == null)
     {
         // make your life easier and pass item in a constructor
         return new Node(item);
     }
     // Do this iff traversedNode != null, which it is in this block
     int compare = item.compareTo(traversedNode.item);
        ... 
     // Now you check to see if compare < 0 and compare > 0
     // then you insert your node accordingly and recursively
     // you need to pass the current node left or right as your new traversedNode
     // eg. traversedNode.left = insert( traversedNode.left, item )
   }

Answer 2

因为你的左边是空的？不应该是这样吗。左=插入（项目）

但代码中还有其他问题。我会留给你去发现的。