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