私はバイナリ検索ツリーのコードを書いていました。しかし、以下のコードでjava.lang.StackOverflowErrorというエラーが1つ発生しています

Question

これはバイナリ検索ツリーの検索と挿入のコードです。私は、関数Node12のinsert2（Node12 curr、int d）を繰り返すことでツリーの左右のノードをチェックしようとしています。 1行にランタイムエラーが表示されます。 助けてください

class bst { 

    class Node12 { 

    Node12 left, right; 
    int data; 

    Node12(int d) { 
     data = d; 
     left = null; 
     right = null; 
    } 
} 

    Node12 root; 

    bst() { 
     root = null; 
    } 

    void Search(int looking) { 
     Node12 current = root; 
     while (current != null) { 
      if (current.data == looking) { 
       System.out.println("Desirable print" + current.data); 

      } else if (current.data > looking) { 
       current = current.left; 
      } else { 
       current = current.right; 
      } 
     } 

    } 

    void insert(int d) { 
     root = insert2(root, d); 
    } 

    Node12 insert2(Node12 curr, int d) { 
     curr = root; 
     if (curr == null) { 
      curr = new Node12(d); 
      return curr; 
     } 
     if (curr.data > d) { 
      curr.left = insert2(curr.left, d); 
     } else if (curr.data < d) { 
      curr.right = insert2(curr.right, d);-----(Here i am getting error) 

     } 

     return curr; 
    } 

    void inorder2() { 
     inorder(root); 
    } 

    void inorder(Node12 current) { 
     current = root; 
     if (current != null) { 
      inorder(current.left); 
      System.out.println(current.data); 
      inorder(current.right); 
     } 
    } 

    public static void main(String... s) { 
     bst b1 = new bst(); 
     b1.insert(10); 
     b1.insert(20); 
     b1.insert(30); 
     b1.insert(40); 
     b1.insert(50); 
     b1.insert(60); 

     b1.inorder2(); 
     b1.Search(25);  
    } 
} 

その宿題に問題があります。だから私はBSTとその実装を理解しようとしています。

Answer 1

基本条件エラーがあると思います。

挿入メソッドを見てください。

void insert(int d) { 
    root = insert2(root, d);  
} 

ルートはすでにルート要素ではありません。それはあなたのツリーの右または左のノードかもしれません。

NODE12インスタンスのCURRパラメータは、左、右、またはルート要素である

Node12 insert2(Node12 curr, int d) { 
    // curr = root; 
    // if (curr == null) { 
    // curr = new Node12(d); 
    // return curr; 
    // } 

    if (curr == null) { 
     curr = new Node12(d); 
     return curr; 
    } 
    System.out.println(curr.data + ":" + d); 

    if (curr.data > d) { 

     curr.left = insert2(curr.left, d); 
    } else if (curr.data < d) { 
     curr.right = insert2(curr.right, d);// -----(Here i am getting error) 

    } 

    return curr; 
} 

に従うように、実際の方法、insert2は、（）でなければなりません。 したがって、基本条件は引数nullまたはnullでないことをチェックするだけです。

また、インオーダーメソッドもinsert2メソッドと同じです。

void inorder(Node12 current) { 
    // current = root; 
    if (current != null) { 
     if (current.left != null) 
      inorder(current.left); 
     System.out.println(current.data); 
     if (current.right != null) 
      inorder(current.right); 
    } 
} 

これだけです。

完全なソースコード：

class bst { 

    class Node12 { 

     Node12 left, right; 
     int data; 

     Node12(int d) { 
      data = d; 
      left = null; 
      right = null; 
     } 
    } 

    Node12 root; 

    bst() { 
     root = null; 
    } 

    void Search(int looking) { 
     Node12 current = root; 
     boolean isFound = false; 
     int data = -1; 

     while (current != null) { 
      if (current.data == looking) { 
       data = current.data; 
       isFound = true; 
       break; 
      } else if (current.data > looking) { 
       current = current.left; 
      } else { 
       current = current.right; 
      } 
     } 

     if (isFound) { 
      System.out.println("Desirable print ::" + data); 
     } 

    } 

    void insert(int d) { 
     root = insert2(root, d); 

    } 

    Node12 insert2(Node12 curr, int d) { 
     // curr = root; 
     // if (curr == null) { 
     // curr = new Node12(d); 
     // return curr; 
     // } 

     if (curr == null) { 
      curr = new Node12(d); 
      return curr; 
     } 


     if (curr.data > d) { 

      curr.left = insert2(curr.left, d); 
     } else if (curr.data < d) { 
      curr.right = insert2(curr.right, d);// -----(Here i am getting error) 

     } 

     return curr; 
    } 

    void inorder2() { 
     inorder(root); 
    } 

    void inorder(Node12 current) { 
     // current = root; 
     if (current != null) { 
      if (current.left != null) 
       inorder(current.left); 
      System.out.println(current.data); 
      if (current.right != null) 
       inorder(current.right); 
     } 
    } 

    public static void main(String... s) { 
     bst b1 = new bst(); 

     b1.insert(10); 
     b1.insert(20); 
     b1.insert(30); 
     b1.insert(40); 
     b1.insert(50); 
     b1.insert(60); 

     b1.inorder2(); 
     b1.Search(50); 
    } 
}