链接二叉搜索树的标准差

Question

我目前正在为我的数据结构课程开展一个项目，该项目涉及使用双向链表类型格式构建的二叉搜索树（其中每个节点都有左指针、右指针和父指针）。 class 管理树也有一个根指针和一个当前指针（像游标）。

我需要构建的函数之一是计算整棵树的标准差。不幸的是，我陷入了如何在不使用标准库容器的情况下处理此功能的问题（在课程中非常不鼓励这样做）。我了解如何获得整棵树的总和，但是能够单独访问每个数字来计算标准偏差让我感到困惑（因为我可以 not 将树存储为数组并按顺序访问内容。

如果这是一个基本问题或者我遗漏了一些明显的方法，请原谅我。我倾向于与数据结构概念作斗争，尤其是在涉及递归时。我不是在要求某人编写该函数，但至少可以为我指明正确的方向。谢谢！

编辑：谢谢 trincot 的帮助，我一直在想错误的方法，但你的解释很有帮助！

Answer 1

I understand how to get the sum of the entire tree

所以你知道如何检查每个节点的值并执行类似的操作：

sum += current_node->value;

然后也跟踪计数（除非您已经将计数作为列表跟踪属性）：

sum += current_node->value;
node_count++;

访问完所有节点后，可以计算均值：

mean = sum / node_count;

然后第二次遍历树的所有节点，计算偏差平方和，从零开始：

sum_sq_dev += (current_node->value - mean) * (current_node->value - mean);

访问所有节点以累积偏差平方和后，计算其方差和标准偏差：

variance = sum_sq_dev / node_count;
std_dev = sqrt(variance);

参见 sample variance

上的维基百科