二叉搜索樹插入錯誤

Question

package array; 

import java.util.Scanner; 

class node<T>{ 
    T data; 
    node<T> left; 
    node<T> right; 
} 
public class binarytree { 

    public static void main(String [] args){ 
    node<Integer> root = null; 
    node<Integer> n = new node<>(); 
    Scanner s = new Scanner(System.in); 
    root=create(s.nextInt()); 
    System.out.println("root creates"); 
    //root=insert(n,root); 
    for(int i =1;i<6;i++){ 
     n=create(s.nextInt()); 
     insert(n,root); 
     System.out.println(i+"th inserted "); 
     inorder(root); 
     System.out.println(); 
    } 
    } 
    private static void inorder(node<Integer> root) { 
     if(root==null){ 
      return; 
     } 
     inorder(root.left); 
     System.out.print(root.data+" "); 
     inorder(root.right); 
     return; 
    } 
    private static void insert(node<Integer> n, node<Integer> root) { 
     if(root.left==null&&root.right==null){//line 37 
      if(root.data>n.data){ 
       root.left=n; 
      } 
      else{ 
       root.right=n; 
      } 

     } 
     else if(root.data>n.data){ 
      insert(n, root.left);//line 47 
     } 
     else{ 
      insert(n, root.right); 
     } 

     return ; 
    } 
    private static node<Integer> create(int data) { 
     node<Integer> n = new node<>(); 
     n.data=data; 
     n.left=n.right=null; 
     return n; 
    } 
} 

代碼工作正常正小整數，但給空指針異常與像某些輸入：

2 -3 1 -44 

和停止，並給出空指針異常。

一些這樣然而

，它工作正常

6 4 3 2 1 

堆棧跟蹤：

Exception in thread "main" java.lang.NullPointerException 
    at array.binarytree.insert(binarytree.java:37) 
    at array.binarytree.insert(binarytree.java:47) 
    at array.binarytree.insert(binarytree.java:47) 
    at array.binarytree.main(binarytree.java:21) 

Answer 1

你如果在INSERT語句短路時root.left == null是假的，並允許root.right告吹，然後在遞歸中傳遞root.right，該值爲null。或者你的樹是空的，根目錄是空的。

嘗試重組，像這樣

private static void insert(node<Integer> n, node<Integer> root) { 
    if (n == null) return; 
    if (root == null) { 
     // TODO: Set the root? 
    } 

    Integer data = n.data; 
    Integer rootData = root.data; 

    if (data < rootData) { 
     if(root.left == null){ 
      root.left = n; 
     } 
     else{ 
      insert(n, root.left); 
     } 
    } 
    else if(data >= rootData){ 
     if (root.right == null) { 
      root.right = n; 
     } else { 
      insert(n, root.right); 
     } 
    } 
}