c++ - 求二叉树c++的平均值

Question

所以我正在尝试编写一个递归函数来返回 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;
}

谢谢你的帮助。

Answer 1

这是一个非常简单的示例，可以说明为什么您计算的不是平均值：

    10
   /  \
  4    12 
         \
          20

在“12”节点处，平均值为(12 + 20) / 2 = 16.

然后在10节点处，平均值将为(4 + 10 + 16) / 3 = 10。

但是，平均水平确实如此11.5。

问题是平均值的平均值不等于一个大的正确平均值。在每个级别，您必须将平均值乘以用于计算它的节点数（即总和），然后才能在下一次平均计算中使用它。

一种更简单的方法可能是计算总和，然后除以树中的节点数。

一种技术的一些伪代码是：

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..
}