バイナリ検索ツリーの挿入エラー

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; 
    } 
} 

コードが正の小さな整数で正常に動作しますが、のような特定の入力でnullポインタ例外を与える：

2 -3 1 -44 

、それがnullポインタ例外を停止しています。

は、しかし、このようないくつかと、それが正常に

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

をごroot.left == nullが偽とroot.rightを通って落下することが可能であるとき、インサート内のステートメントは短絡である場合、そしてあなたはnullである再帰でroot.rightを渡します。またはあなたのツリーは空であり、ルートは単にヌルです。そう

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); 
     } 
    } 
}