1

そのため、C++ で値のバイナリ ツリーの平均値を返す再帰関数を作成しようとしています。ここに私が持っているものがありますが、それはうまくいきません:

double avg(bNode* root)
{
    if(!root) return 0;
    int sum = avg(root->left) + avg(root->right) + root->value;
    if(root->left && root->right) return sum/3;
    else if(!root->left && !root->right) return sum;
    else return sum/2;
}

ご協力いただきありがとうございます。

4

1 に答える 1

1

計算しているものが平均ではない理由を示す非常に単純な例を次に示します。

    10
   /  \
  4    12 
         \
          20

「12」ノードでは、平均は になります(12 + 20) / 2 = 16。

次に、10ノードでの平均は になります(4 + 10 + 16) / 3 = 10。

しかし、平均は本当に11.5.

問題は、平均の平均の平均が 1 つの大きな正しい平均に等しくないことです。各レベルで、次の平均計算で使用する前に、平均を計算に使用されたノードの数 (合計) で乗算する必要があります。

これを行う簡単な方法は、おそらく合計を計算してから、ツリー内のノード数で割ることです。

これを行う 1 つの手法の疑似コードは次のようになります。

class accumulator
{
    int sum = 0;
    int count = 0;

    // implement the obvious operator+
};

accumulator avg(bNode* root)
{
    if(!root) return <empty accumulator>
    return <recursive children> + <self>;
}

int main()
{
    accumulator acc = avg(root);
    // ..calculate average..
}
于 2013-01-25T04:14:10.000 に答える