实现二叉搜索树插入

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，那么它没有值。