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 ファイルのサイズは? ファイルが大きいほど、再帰が深くなり、スタックオーバーフローが発生します。

次のコマンド ライン パラメータを使用して 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 に答える