實現二叉搜索樹插入

Question

我想編寫二叉搜索樹的代碼，我正在處理的第一個方法是添加（插入）方法。根似乎正確插入，但我添加第二個節點時收到空指針異常。我將在代碼中註明確切的問題點。

如果你能看到如何解決這些bug，或者讓我知道我的整體邏輯是否有缺陷，那將是非常有用的 - 我會提到這是爲了學校，所以我不打算做真正令人印象深刻的模型......我的大部分佈局選擇都反映了我們在課堂上工作的方式。此外，方法名稱由老師選擇，並應保持不變。隨意編輯格式，有點麻煩。

二叉樹類

public class BinarySearchTree 
{ 
private static Node root; 

    public BinarySearchTree() 
    { 
     root = null; 
    } 

    public static void Add (Node newNode) 
    { 
     Node k = root; 
     if (root == null)//-----------------IF TREE IS EMPTY ----------------- 
     { 
      root = newNode; 
     } 

     else // -------TREE IS NOT EMPTY -------- 

     { 
     if (newNode.value > k.value) //-------NEW NODE IS LARGER THAN ROOT--------- 
     { 
      boolean searching = true; 

      while(searching) // SEARCH UNTIL K HAS A LARGER VALUE 
      { //***CODE FAILS HERE**** 
       if(k.value > newNode.value || k == null) 
       { 
        searching = false; 
       } 
       else {k = k.rightChild; } 
      } 

      if (k == null) { k = newNode;} 
      else if (k.leftChild == null){ k.leftChild = newNode;} 
      else 
      { 
       Node temp = k.leftChild; 
       k.leftChild = newNode; 
       newNode = k.leftChild; 

       if(temp.value > newNode.value) 
       { 
        newNode.rightChild = temp; 
       } 
       else 
       { 
        newNode.leftChild = temp; 
       } 
      } 

     } 

     if (newNode.value < k.value) //-----IF NEW NODE IS SMALLER THAN ROOT--- 
     { 
      boolean searching = true; 

      while(searching) // ----SEARCH UNTIL K HAS SMALLER VALUE 
      {// **** CODE WILL PROBABLY FAIL HERE TOO *** 
       if(k.value < newNode.value || k == null) {searching = false;} 
       else {k = k.leftChild;} 
      } 

      if (k == null) { k = newNode;} 
      else if (k.rightChild == null){ k.rightChild = newNode;} 
      else 
      { 
       Node temp = k.rightChild; 
       k.rightChild = newNode; 
       newNode = k.rightChild; 

       if(temp.value > newNode.value) 
       { 
        newNode.rightChild = temp; 
       } 
       else 
       { 
        newNode.leftChild = temp; 
       } 
      } 
     }  
      }} // sorry having formatting issues 
} 

節點類

public class Node 
{ 
    int value; 
    Node leftChild; 
    Node rightChild; 

    public Node (int VALUE) 
    { 
       value = VALUE; 
    } 
} 

試驗中的應用

public class TestIT 
{ 

    public static void main(String[] args) 
    { 

     BinarySearchTree tree1 = new BinarySearchTree(); 
     Node five = new Node(5); 
     Node six = new Node(6); 

     tree1.Add(five); 
     tree1.Add(six); 

     System.out.println("five value: " + five.value); 
     System.out.println("five right: " + five.rightChild.value); 
    } 

} 

Answer 1

的條件語句從左到右檢查，所以你需要檢查k是否在檢查是否k.value> newNode.value之前爲null，因爲如果k爲null，那麼它沒有值。