树数据结构中的节点总数？

Question

我有一个L层深度的树数据结构,每个节点有大约 N个节点.我想计算树中的节点总数.要做到这一点(我认为),我需要知道有孩子的节点的百分比.

N中叶节点与非叶节点的比率的正确项是什么？

计算三者中节点总数的公式是什么？

更新有人在其中一个答案中提到分支因素,但随后消失了.我想这就是我要找的那个词.那么一个公式不应该考虑分支因素吗？

更新我应该说一个关于假设数据结构的估计,而不是确切的数字!

Answer 1

好的,每个节点有大约N个子节点,树是L级深度.

With 1 level, the tree has 1 node.
With 2 levels, the tree has 1 + N nodes.
With 3 levels, the tree has 1 + N + N^2 nodes.
With L levels, the tree has 1 + N + N^2 + ... + N^(L-1) nodes.

节点总数为(N ^ L-1)/(N-1).

好吧,只是一个小例子,它是指数的:

                    [NODE]
                      |
                     /|\
                    / | \
                   /  |  \
                  /   |   \
            [NODE]  [NODE] [NODE]
              |
             /|\
            / | \

Answer 2

只是为了纠正第一个答案中的拼写错误:深度为L的树的节点总数是(N ^(L + 1)-1)/(N-1)...(即,对于幂L +1而不仅仅是L).

这可以显示如下.首先,采取我们的定理:

1 + N ^ 1 + N ^ 2 + ... + N ^ L =(N ^(L + 1)-1)/(N-1)

将两边乘以(N-1):

(N-1)(1 + N ^ 1 + N ^ 2 + ... + N ^ L)= N ^(L + 1)-1.

展开左侧:

N ^ 1 + N ^ 2 + N ^ 3 + ... + N ^(L + 1) - 1 - N ^ 1 - N ^ 2 - ... - N ^ L.

所有项N ^ 1到N ^ L都被抵消,留下N ^(L + 1) - 1.这是我们的右手边,所以初始相等是正确的.