我正在编写二叉搜索树的代码。但我在下面的代码中得到一个错误是java.lang.StackOverflowError

Question

这是二进制搜索树搜索和插入的代码。当我试图通过重复函数Node12 insert2（Node12 curr，int d）检查树的左右节点时。在一行中显示运行时错误。 请帮忙

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

根已经不是根元素了。它可能是你的树的右或左节点。

所以，实际的方法，insert2（）必须是如下

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

的Node12实例的CURR参数是左，右或根元素。 所以，你的基础条件只是检查参数为null或不为null。

而inorder方法也与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); 
    } 
}