1

我目前正在开发一个在添加和删除值时显示堆的小程序。我将堆实现为整数树 - IntTrees。我正在为倾斜堆编写代码，而“添加”方法给我带来了一些麻烦。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 回答