バイナリーサーチツリーで高さを探す

Question

さらに

ソース非AMP版編集

バイナリーサーチツリーで高さを探す

二分探索木の高さを求める方法を作り直したいのですが、どなたか手伝っていただけないでしょうか。今のところ、私のコードは次のようになっています。しかし，得られる答えは実際の高さよりも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;
    }
}

altern

編集された質問 15日 8月 2017 в 8:09

プログラミング

binary-tree

8日 4月 2010 в 4:47

6 ビュー

Stephen · Answer 1 · 2010-04-08T05:08:46+00:00

二分探索木の高さは，「層の数-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));
}

Jerry Coffin · Answer 2 · 2010-04-08T05:06:20+00:00

私の意見では、あなたのコードは少しシンプルにした方が良いと思います。子ポインタがnullになったときに再帰を終了させるのではなく、current***ポインタがnullになったときにのみ再帰を終了させるようにします。そうすれば、コードはずっとシンプルに書けるようになります。疑似コードでは次のようになります。

if (node = null)
    return 0;
else
    left = height(node->left);
    right = height(node->right);
    return 1 + max(left, right);

Matthew Flaschen · Answer 3 · 2010-04-08T04:51:06+00:00

ここでは、それを簡潔に、できれば正しく表現しています。

  private int findHeight(TreeNode 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として使用しています。