StackOverflowError - 將值添加到堆

Question

我目前正在研究一個applet，它會在添加和刪除值時顯示一個堆。我正在實施堆整數樹 - 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; 
    } 

在這段代碼中是否會引起堆棧溢出錯誤，或者是程序中其他地方的問題？謝謝！

Answer 1

看看這個片斷

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

時會發生什麼rightVal == leftVal？

Answer 2

@Adam找到了你的問題。這是爲了幫助你自己找到這樣的問題。

當您發現意外錯誤或異常時，仔細研究堆棧跟蹤非常重要。如果你知道如何閱讀，經常會有堆棧跟蹤中的大量信息。

在這種情況下，您會看到merge方法有許多堆棧幀。如果仔細看過它們，您會注意到merge從同一行代碼中一遍又一遍地調用merge。這是遞歸循環的經典標誌。

鑑於這些線索（特別是發生遞歸的行號），找出爲什麼有一個遞歸循環將是一件簡單的事情。