0

ノードの数が与えられると、log2(n) を実行することでバイナリ ツリーの最小の深さを計算できます。

ここで、n はノード数です。

たとえば 12 ノードの最大深度でツリーを描画すると、ツリーのバランスを維持する場合、最大深度は 4 しかないことがわかります。

                0
               /   \
              0     0
            /  \   / \
           0    0 0   0
          /\     \     \ 
        0   0      0    0

悪いASCIIアートでごめんなさい。ノード数が与えられたときにバイナリツリーの最大深度を計算できるフォーラムを知っている人はいますか? または、少なくとも私を正しい方向に向けますか？

4

3 に答える 3

3

ルート要素を使用して:

int maxHeight(BinaryTree *p) {
  if (!p) return 0;
  int left_height = maxHeight(p->left);
  int right_height = maxHeight(p->right);
  return (left_height > right_height) ? left_height + 1 : right_height + 1;
}

ノード数といくつかの数学ロジックを使用することにより(これは正確に表現できません (私は決して数学の第一人者ではありません); しかし、ここにあります):

観察 ：

  • 2 ～ 3 ノード => maxDepth = 1 (2 = 2^1、3 = 2^1、.. < 2^2 )
  • 4 ～ 7 ノード => maxDepth = 2 (4 = 2^2、5 = 2^2、..、6 = 2^2、..、7 = 2^2、... < 2^3)
  • 8 ～ 15 ノード => maxDepth = 3
  • ...

分析 ：

  • m => max Depth (深さの実際の INT 部分、小数点以下の桁数は破棄)

  • n => ノード数

  • ln => 自然対数 (=log[e])

  • 2^m = n

  • ln(2^m) = ln(n)

  • m*ln(2) = ln(n)
  • m = ln(n)/ln(2)

結論 ：

ここで、m = 2,... の場合、最大深度は 2 です。その int 部分を取得するだけです。;-)

注:私は間違いなく車輪を再発明しています。しかし、それはおそらく、何も知らないことを扱う楽しみの一部です。そして、あなたの本能と観察だけに従って、それを行います... :-)

于 2012-03-23T11:11:34.817 に答える
2

最も簡単な答えは次のようになります。

int getMaxDepth(Node node)
{
    if(node == null) {
        return 0;
    }

    int leftDepth = 1 + getMaxDepth(node.left);
    int rightDepth = 1 + getMaxDepth(node.right);

    return left > right ? left : right;
}

コンセプトの説明

于 2013-07-13T19:21:43.027 に答える