이진 검색 트리 삽입을 구현

Question

나는 이진 검색 트리에 대한 코드를 작성하려고하는데, 내가하고있는 첫 번째 방법은 add (insert) 메소드이다. 루트 제대로 삽입 할 것으로 보인다 있지만 두 번째 노드를 추가 할 때 널 포인터 예외가 발생합니다. 의견과 함께 내 코드에서 정확한 문제 지점을 나타냅니다.

버그를 수정하는 방법을 볼 수 있거나 전반적인 논리에 결함이 있는지 알려면 엄청난 도움이 될 것입니다 .-이 내용은 학교용이므로 언급 할 부분이 없습니다. 정말 인상적인 모델 ... 대부분의 레이아웃 선택은 단순히 우리가 수업에서 일하는 방식을 반영합니다. 또한 메소드 이름은 교사가 선택 했으므로 그대로 유지해야합니다. 약간의 문제가 있어도 서식을 편집 할 수 있습니다.

이진 트리 클래스

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 
} 

노드 CLASS

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가 null의 경우는 값을 가지지 않기 때문에, k.value> newNode.value인지 어떤지를 확인하기 전에 null을 돌려 준다.