スタックオーバーフローバイナリ検索ツリーの計算深さ

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

の初心者レベルを許します確かに理由

これはあなたがは、calcDepthの引数として、常にと同じで、this.leftとthis.rightを渡します。また、this.keyはです。常にと同じですので、基本的には常にです。実際にはツリーを横切ることなく2つのキー（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を返すことができます。

注 - 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; 
}