二分探索木の高さを求める方法を作り直したいのですが、どなたか手伝っていただけないでしょうか。今のところ、私のコードは次のようになっています。しかし,得られる答えは実際の高さよりも1だけ大きいのです。しかし,return文から+1を取り除くと,実際の高さよりも1だけ小さくなります。これらのBSTを使った再帰については,まだ理解できていません。何かアドバイスがあればお願いします。
public int findHeight(){
if(this.isEmpty()){
return 0;
}
else{
TreeNode<T> node = root;
return findHeight(node);
}
}
private int findHeight(TreeNode<T> aNode){
int heightLeft = 0;
int heightRight = 0;
if(aNode.left!=null)
heightLeft = findHeight(aNode.left);
if(aNode.right!=null)
heightRight = findHeight(aNode.right);
if(heightLeft > heightRight){
return heightLeft+1;
}
else{
return heightRight+1;
}
}
二分探索木の高さは,「層の数-1」に等しい。
http://en.wikipedia.org/wiki/Binary_tree の図を参照してください。
あなたの再帰性は良好なので、ルートレベルで1を引くだけです。
また、NULLノードを処理することで、この関数を少しきれいにすることができます。
int findHeight(node) {
if (node == null) return 0;
return 1 + max(findHeight(node.left), findHeight(node.right));
}
私の意見では、あなたのコードは少しシンプルにした方が良いと思います。子ポインタがnullになったときに再帰を終了させるのではなく、current***ポインタがnullになったときにのみ再帰を終了させるようにします。そうすれば、コードはずっとシンプルに書けるようになります。疑似コードでは次のようになります。
if (node = null)
return 0;
else
left = height(node->left);
right = height(node->right);
return 1 + max(left, right);
ここでは、それを簡潔に、できれば正しく表現しています。
private int findHeight(TreeNode<T> aNode){
if(aNode == null || (aNode.left == null && aNode.right == null))
return 0;
return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1;
}
カレントノードがNULLの場合、ツリーは存在しません。 子ノードが両方ともnullの場合は、1つのレイヤーがあり、高さは0です。 これは、高さの定義(Stephenが言及している)を# of layers - 1として使用しています。