递归函数中的stackoverflow错误

Question

我有以下功能 class 实现一组数字作为二进制搜索 tree.The 功能检查输入整数是否在树中。

 public boolean isIn(int v){

     if(root != null){  
        if(v == root.element){
            System.out.print(root.element);
            return true;
        }
        isIn(root.left.element);
        isIn(root.right.element);
       }
       return false;
     }

如果我使用该函数检查树的第一个元素以外的任何内容，我将在线程 "main" java.lang.WhosebugError 中收到 异常。

编辑：我的树设置如下：

public class BSTSet{ private TNode root; public BSTSet(){ root = null; } public BSTSet(int[] input){ int len = input.length; for (int i = 0; i<len-1; i++ ) { add(input[i]); } } public void add(int v) { if (root == null) { root = new TNode( v, null,null); return; } TNode node = root; while (true) { if (v < node.element) { if (node.left == null) { node.left = new TNode( v, null,null); break; } node = node.left; } else if(v>node.element){ if (node.right == null) { node.right = new TNode(v, null,null); break; } node = node.right; } else{ break; } } }

Answer 1

你有一些问题。您只是将每个参数与 root.element 进行比较。另外，v应该是用户要搜索的int，你传入的是树的不同元素，而不是用户搜索的值：

isIn(root.left.element);
isIn(root.right.element);

您还忽略了递归调用的结果。你需要重新考虑一下你的逻辑。您希望将 Node 和 int（搜索值）传递给该方法。您可以为此使用重载方法：

public boolean isIn(int v){
    return isIn(v, root);
}

然后有：

public boolean isIn(int v, Node node){
    if(node != null){  
        if(v == node.element){
            System.out.print(node.element);
            return true;
        }
        return isIn(v, node.left) || isIn(v, node.right);

    }
    return false;
}

递归函数中的stackoverflow错误

stackoverflow error in recursive function

java

stack-overflow

binary-search-tree