0

我是树的初学者，我只是第一次尝试实现一个并正在生成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();
}
4

4 回答 4

1

如果文件最初是排序的，那么这个函数看起来会为一个有 N 行的文件递归 N 次。Java 没有实现尾递归，所以这肯定是一个真正的递归。将其重写为 while 循环而不是递归函数。

于 2012-08-10T23:21:22.353 回答
0

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

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

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

于 2012-08-10T23:15:50.497 回答
0

这个 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);
}
于 2012-08-10T23:18:41.707 回答
0

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

红黑树通过重新分配元素自动平衡树来避免这个问题。然而，编写这样一个数据结构并不是那么简单。

于 2012-08-10T23:50:41.950 回答