遞歸計算多態bst對象的深度

我想計算一個多態bst中的鍵的深度（而不是空對象空對象用EmptyTrees表示），我不知道如何實現實際的代碼。遞歸計算多態bst對象的深度

private int calcDepth(K keyIn, int level){ 
if (this.key.compareTo(keyIn) == 0) return level; 

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

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

    return -1; 
}

我很新到Java所以原諒的問題

所以我的問題是，我怎麼計算我的BST一個關鍵的深度基本和或神志不清的性質？

來源

2017-04-11 emmynaki

這裏有什麼具體問題？ –

我將如何計算我bst的密鑰的深度 – emmynaki

現在你有什麼不對？ –

好了，問題是用代碼的calcDepth方法中這兩條線，

return left.calcDepth(keyIn, level+1);

和

return right.calcDepth(keyIn, level+1);

您只能在有calcDepth方法調用的對象calcDepth。但是，因爲calcDepth僅在NonEmptyTree中定義，所以當您到達分支末端並碰到EmptyTree時會發生什麼？這是您將收到錯誤的地方，因爲EmptyTree沒有此方法。這讓我花了一段時間才意識到，因爲錯誤沒有說明這一點，但由於它是Tree<K,V>的一個子類，它直接表示該方法不存在於超類中。所以，我有兩個建議，要麼

把calcDepth方法在超Tree使兩個子類可以訪問它

或

之前進行遞歸調用，首先檢查left或right是否爲EmptyTree。如果是，那麼在這種情況下返回level+1（假設您將空節點作爲額外級別計數，如果不是則返回level）。

來源

2017-04-11 21:14:56

遞歸計算多態bst對象的深度

回答

相關問題