堆棧溢出二叉搜索樹計算深度

Question

我想計算二叉搜索樹的一個關鍵的深度和我得到一個堆棧溢出錯誤，我不知道爲什麼。這是我目前的代碼。

private int calcDepth(Tree<K, V> x, K keyIn, int currentLevel){ 
    //BASE CASE 
    if (this.key.compareTo(keyIn) == 0) return currentLevel; 

    if (this.key.compareTo(keyIn) < 0){ 
    return calcDepth(this.left, keyIn, currentLevel+1); 
    } 

    if (this.key.compareTo(keyIn) > 0){ 
    return calcDepth(this.right, keyIn, currentLevel + 1); 
    } 

    return -1; 
} 

，這是我的算法

//ALGORITHIM 
//1. if the current key is equal to the parameter key 
// return the currentLevel 
//2. if the current key is less than the parameter key 
// go left and increment the level 
//3. if the current key is greater than the paramete key 
// go right and increment the level 
//4. if none of these cases are met (key is not in tree 
// return -1 

我是新來的Java所以原諒問題的初級水平

Answer 1

我得到一個堆棧溢出錯誤，我不肯定爲什麼

這是由於這樣的事實，你是a lways傳遞this.left和this.right作爲參數的方法calcDepth這是總是相同。另外，this.key是總是是一樣的，所以基本上你是總是比較兩個鍵（this.key和keyIn）而沒有實際向下遍歷樹。即它應該是：

if (x.key.compareTo(keyIn) == 0) 

那麼當你調用：

calcDepth(x.left, keyIn, currentLevel+1); 

或

calcDepth(x.right, keyIn, currentLevel + 1); 

x是在方法的每次調用不同的實例。

看來你沒有對參數x做任何事情。你應該使用x.key（其中x表示樹的當前實例）。

現在x.left和x.right將在方法的每次調用不同的，所以基本上我們要縮小的問題，並達到對基本情況，因此該方法就能風回調用方法和最終結束沒有StackOverflow異常。

最後但並非最不重要的是，您的代碼中存在額外的錯誤，如果給定的key不存在，算法將無法返回-1。爲了克服這個問題簡單地插入，將檢查的情況，如果當前tree爲空，如果這是我們沒有發現我們的key，我們可以簡單地返回-1的情況。

note - 這也將防止NullPointerException的可能性。

private int calcDepth(Tree<K, V> x, K keyIn, int currentLevel){ 

    if(x == null) return -1; // key doesnt exist if this is true 

    if (x.key.compareTo(keyIn) == 0) return currentLevel; //BASE CASE 

    if (x.key.compareTo(keyIn) < 0){ // check left tree 
     return calcDepth(x.left, keyIn, currentLevel+1); 
    } 

    if (x.key.compareTo(keyIn) > 0){ // check right tree 
     return calcDepth(x.right, keyIn, currentLevel + 1); 
    } 

    return -1; 
}