好的，每个节点大约有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]
              |
             /|
            / | 

只是为了更正第一个答案中的打字错误：深度为L的树的总节点数为(N^(L + 1) - 1) / (N-1) …(也就是说，乘以L + 1的幂而不仅仅是L)。

这可以通过以下方式展示。首先，取我们的定理：

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

把两边乘以(N-1)：

(N-1)(1 + N^1 + N^2 + ... + N^L) = N^(L+1)-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^2 + N^3 + ... + N^(L+1) - 1 - N^1 - N^2 - ... - N^L.

所有的项从N^1到N^L都被抵消了，只剩下N ^(L+1) - 1。这是我们的右手边，因此最初的等式是正确的。

如果你的树大致上是满的，也就是除了最后两层以外每一层都有与节点数相等的子节点数，则你的树将会有N^(L-2)到N^(L-1)个叶节点和N^(L-1)到N^L个总节点数。

如果你的树没有满的话，就算知道叶子节点的数量也没有用，因为一棵非平衡树只有一个叶子节点但可以有任意数量的父节点。

我想知道你关于每个节点大约有N个节点的说法有多准确——如果你知道平均分支因子，也许你可以计算预期树的大小。

如果您能够找到叶子节点与内部节点的比率，并且知道平均子节点数，您可以将其近似为（n * 比率）^ N = n。这不会给您答案，但我想知道是否有比我更好的数学能力的人可以想出一种将 L 插入此方程并给出可解决的东西的方法。

然而，如果您想要精确地知道，您必须迭代树的结构并在移动时计算节点。

计算深度 L 中节点数量的公式为：（假设根节点数量为 N）

N的L次方

要计算所有节点的数量，需要对每一层进行这样的操作：

for depth in (1..L)
    nodeCount += N ** depth

如果只有1个根节点，则从L中减去1，并将总节点数加1。

请注意，如果一个节点中的叶子数量与平均情况不同，这可能会对数字产生重大影响。越往树上走影响越大。

     *                *                 *         N ** 1
    ***              ***               ***        N ** 2
*** *** ***      *** *** ***       *** *** ***    N ** 3

这是一个社区维基，所以请随意修改我的可怕的代数。

Knuth 的估计量[1],[2] 是一个针对任意有限树中节点数量的點估计，无需遍历所有节点，甚至无需考虑树是否平衡。Knuth 的估计量是一个无偏估计量；Knuth 的估计量的期望值将是树中节点的数量。话虽如此，如果问题中的树不平衡，Knuth 的估计量可能会有很大的方差，但在您的情况下，因为每个节点将有大约 N 个子节点，我不认为 Knuth 的估计量的方差会太大。当您试图测量执行暴力搜索所需时间的数量时，此估计量尤其有帮助。

For the following functions, we shall assume all trees are represented as lists of lists. For example, [] denotes the tree with the single node, and [[],[[],[]]] will denote a tree with 5 nodes and 3 leaves (the nodes in the tree are in a one-to-one correspondence with the left brackets). The following functions are written in the language GAP.

函数simpleestimate输出估计树tree中节点数量的值。 simpleestimate的思想是随机选择从树的根节点x_0到叶节点x_n的路径x_0，x_1，...，x_n。 假设x_i有a_i个后继节点。 那么simpleestimate将返回1+a_1+a_1*a_2+...+a_1*a_2 *…*a_n。

point:=tree; prod:=1; count:=1; list:=[]; 
while Length(point)>0 do prod:=prod*Length(point); count:=count+prod; point:=Random(point); od;
return count; end;

函数estimate将简单给出通过应用函数simpleestimate(tree) samplesize多次得到的估计值的算术平均值。

estimate:=function(samplesize,tree) local count,i; 
count:=0; 
for i in [1..samplesize] do count:=count+simpleestimate(tree); od; 
return Float(count/samplesize); end;

Example: simpleestimate([[[],[[],[]]],[[[],[]],[]]]); returns 15 while estimate(10000,[[[],[[],[]]],[[[],[]],[]]]); returns 10.9608 (and the tree actually does have 11 nodes).

1. Estimating Search Tree Size. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.129.5569&rep=rep1&type=pdf

2. Estimating the Efficiency of Backtrack Programs. Donald E. Knuth http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0373371-6/S0025-5718-1975-0373371-6.pdf

如果你只知道树的深度，那么计算总大小的唯一选择就是逐个遍历并计数。