이진 검색 트리 삽입 오류

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 

과 중지하고 nullpointer 예외를 제공합니다. 이 같은 일부 그러나

는 그것을 잘

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을 허용하는 경우 삽입의 문이 단락 인 경우 , 그리고 재귀에서 root.right을 전달합니다. 이것은 null입니다. 또는 트리가 비어 있고 루트가 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); 
     } 
    } 
}