这为什么会产生StackOverflowError

Question

我是一个树木初学者，我只是第一次尝试实现它，并且正在生成stackoverfloweror。我知道它可能与错误的递归调用有关，但是我看不到递归有什么问题，请问我能得到些帮助吗？错误在此代码中。

public void insert(Node node, String value)
{
    if((value.compareTo(node.getValue())) < 0)
    {
        if (node.left != null) 
        {
            insert(node.left, value);
        }
        else
            node.left = new Node(value);

    }
    else if((value.compareTo(node.getValue())) > 0)
    {
        if(node.right !=null)
        {
            insert(node.right, value);
        }
        else
            node.right= new Node(value);
    }
}

我在这里称该方法

public static void main(String[] args) throws FileNotFoundException, IOException {
    Tree dataTree = new  Tree(new Node("m"));


    File file = new File("C:\\randomdata.csv");

    BufferedReader br = new BufferedReader(new FileReader(file));
    String line;

    while((line = br.readLine()) != null){
        if(line.toString().contains("zogeti"))
            break;
        else
        {
            dataTree.insert(dataTree.getRootElement(),line);
        }
    }

    br.close();
}

Answer 1

如果文件最初进行了排序，则此函数看起来将递归N次，有N行的文件。 Java没有实现尾递归，因此这肯定是真实的递归。将其重写为while循环，而不是递归函数。

Answer 2

如果您的树中有node.left == node或node.right == node或其他更长的周期，则很可能会发生这种情况。

以其当前形式，如果值相等，则它不会触发if块，只会返回（也返回跟踪）而不会添加任何内容。这意味着该循环可能正在此方法之外发生。

您可能会在可能会在插入网络之外创建元素的唯一其他地方找到此错误：Tree类的构造函数。

Answer 3

此CSV文件有多大？文件越大，递归越深，从而导致stackoverflow。

尝试使用以下命令行参数执行Java。

-Xms512m -Xmx512m

此外，如果从文件读取的新行与现有节点值相同怎么办？

以下代码将忽略...（可能是一个要求，我只是说）。

if((value.compareTo(node.getValue())) < 0)
{
    if (node.left != null) 
    {
        insert(node.left, value);
    }
    else
        node.left = new Node(value);

}
else if((value.compareTo(node.getValue())) > 0)
{
    if(node.right !=null)
    {
        insert(node.right, value);
    }
    else
        node.right= new Node(value);
}

Answer 4

如果文件长3260953行并经过排序，那肯定可以解释您的问题。如果元素按升序排列，则每次insert插入新元素时，每次都会将其放置在每个节点的右分支上。最后得到的是一个字符串3260953线性链接的节点，您的代码可以通过许多递归调用来访问这些节点。这将使堆栈溢出。尝试以乱码的字母顺序在更小的文件上运行。

Red-Black Trees通过重新分配元素自动平衡树来避免此问题。但是，编写这样的数据结构并不是那么简单。