data-structures - 树数据结构中的节点总数？

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]
              |
             /|\
            / | \