插入BST無頭節點JAVA

我正在爲BST的遞歸插入方法。假設這個函數是一個遞歸輔助方法，並且在一個名爲Node的私有類中。 Node類位於一個名爲BinarySearchTree的類中，該類包含一個根實例變量。當我試圖插入一個元素，我在得到一個NullPointerException：插入BST無頭節點JAVA

this.left（插入）（（（節點）左）.element）;

我不確定爲什麼發生這種情況。如果我理解正確，在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; 
    } 
}

來源

2012-10-24 Petiatil

Coz ur left is null？不應該是this.left =插入（item）

但是在代碼中還存在其他問題。我會留下這個給你看看。

來源

2012-10-24 04:48:20 smk

當我檢查我的if語句中的null（即if（left == null））時，我創建了一個新節點。但是，問題依然存在。 – Petiatil

這是因爲您在插入成功之前正在從空對象讀取參數。而且你的左右兩邊都是空的，所以我會留給你弄清楚，但想一想。您應該插入new Node(item)。如果你的函數是遞歸的，那麼你需要傳入當前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) 
    }

來源

2012-10-24 04:51:27 KappaMax

如果我理解正確，我檢查橫向的方向（做比較）iff root不爲null，然後取當前parentNode並進行項目比較。 >如果比較小於0 如果項目爲空然後創建一個新節點否則調用插入 – Petiatil

我編輯了代碼以使它更清楚步驟的順序應該是什麼。當然，你會看到你的方法簽名必須改變，並且你第一次調用你在'（root，item）'中傳遞的方法作爲參數。 – KappaMax

插入BST無頭節點JAVA

回答

相關問題