1

私は現在、値が追加および削除されたときにヒープを表示するアプレットに取り組んでいます。ヒープを整数のツリー（IntTrees）として実装しています。スキューヒープのコードを書いていますが、「add」メソッドを使用すると問題が発生します。addメソッドは通常は機能しますが、値が追加されるとスタックオーバーフローエラーが発生することがあり、その理由がわかりません。

これが私がaddメソッドのために書いたコードです

「t」はインスタンス変数、つまりヒープ自体です。

 // adds value to heap
 public void add(int value) {

IntTree smallTree = new IntTree(value, empty(), empty());

 if (t == null) {
  t = smallTree;
 } else {
  t = merge(t, smallTree);
  }
}

public IntTree merge(IntTree left, IntTree right) {

if (isEmpty(left)) return right;
if (isEmpty(right)) return left;

int leftVal = left.value();
int rightVal = right.value();
IntTree result;

if (rightVal <= leftVal) {
  result = merge(right,left);
} else {
  result = left;

  if (result.isEmpty(left)) {
    result.setLeft(right);
  } else {
    IntTree temp = result.right();
    result.setRight(result.left());
    result.setLeft(merge(temp,right));
  }
}

    return result;
  }

このコードにスタックオーバーフローエラーを引き起こす何かがありますか、それともプログラムの他の場所に問題がありますか？ありがとう！

4

2 に答える 2

2

このスニペットを見てください

if (rightVal <= leftVal) {
  result = merge(right,left);

いつ何が起こりrightVal == leftValますか？

于 2010-11-03T02:12:02.760 に答える
2

@Adamはあなたのために問題を見つけました。これは、このような問題を自分で見つけるのに役立ちます。

予期しないエラーや例外が発生した場合は、スタックトレースを注意深く調べることが重要です。スタックトレースには多くの情報が含まれていることがよくあります...それを読み取る方法を知っている場合。

この場合、メソッドには非常に多くのスタックフレームがあることがわかりますmerge。それらを注意深く見ていれば、同じコード行から何度も何度もmerge呼び出していることに気付くでしょう。mergeこれは、再帰ループの典型的な兆候です。

これらの手がかり（特に再帰が発生した行番号）を考えると、再帰ループが発生した理由を理解するのは簡単なことでした。

于 2010-11-03T03:13:08.147 に答える