algorithm - 获取二叉搜索树的平均高度

Question

我遇到了一个问题陈述，其中树的形式是：

     4
  2     6
1   3 5   7

它说平均高度是1.4285715

据我所知，一棵树的平均高度是每个节点的高度之和除以节点总数。但是我得到了不同的结果。我需要有关如何计算值 1.4285715 的提示。

Answer 1

根节点通常不包含在高度中，但在计算节点时会包含它。因此，我们有两个高度为 1 的节点和四个高度为 2 的节点：

(2 * 1) + (4 * 2) = 10
10 / 7            = 1.4285714286

在http://en.wikipedia.org/wiki/Binary_tree阅读更多内容

Answer 2

     4        // 0
  2     6     // 1
1   3 5   7   // 2

(0 + 1 + 1 + 2 + 2 + 2 + 2) / 7 = 1.4285715

Answer 3

使用您的公式将根深度设置为 0: (0 + 1 + 1 + 2 + 2 + 2 + 2) / 7 = 10 / 7 = 1.4285715。