我有一个树状数据结构，L级深，每个节点都有 about N个节点 . 我想计算树中的节点总数 . 要做到这一点（我认为），我需要知道有孩子的节点的百分比 .
N中叶节点与非叶节点的比率的正确项是什么？
计算三者中节点总数的公式是什么？
Update 有人在其中一个答案中提到了 Branching factor 但它随后消失了 . 我想这就是我要找的那个词 . 那么一个公式不应该考虑分支因素吗？
Update 我应该说一个关于假设数据结构的估计，而不是确切的数字！
只是为了纠正第一个答案中的拼写错误：深度为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.这是我们的右手边，所以初始相等是正确的 .
好的，每个节点有大约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] | /|\ / | \
如果你的树几乎已满，那就是除了最后两个之外，每个级别都有其完整的子级，那么你有N ^（L-2）和N ^（L-1）个叶子节点之间和N ^（L -1）和N ^ L个节点总数 .
如果你的树没有满，那么知道叶子节点的数量并没有帮助，因为完全不 balancer 的树将有一个叶子节点但是任意多个父节点 .
我想知道你的'每个节点有关N个节点'的说法有多精确 - 如果你知道平均分支因子，也许你可以计算树的预期大小 .
如果您能够找到叶子与内部节点的比率，并且您知道平均子节点数，则可以将其近似为（n * ratio）^ N = n . 这不会给你你的答案，但我想知道如果有一个比我更好的数学的人能找到一种方法将L插入这个等式并给你一些可溶的东西 .
但是，如果您想要精确地知道，您必须迭代树的结构并随时计算节点 .
计算深度为L的节点数量的公式为:(假设有N个根节点）
NL
要计算每个层需要执行此操作的所有节点的数量：
for depth in (1..L) nodeCount += N ** depth
如果只有一个根节点，则从L中减去1并将总节点数加1 .
请注意，如果在一个节点中叶子的数量与平均情况不同，则会对您的数量产生很大影响 . 在树中越往上越具有影响力 .
* * * N ** 1 *** *** *** N ** 2 *** *** *** *** *** *** *** *** *** N ** 3
这是社区维基，所以随时改变我令人讨厌的代数 .
如果除了树的深度之外你什么都不知道，那么计算总大小的唯一选择就是通过计算它们 .
5 回答
只是为了纠正第一个答案中的拼写错误：深度为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.这是我们的右手边，所以初始相等是正确的 .
好的，每个节点有大约N个子节点，树是L级深度 .
节点总数为（N ^ L-1）/（N-1） .
好吧，只是一个小例子，它是指数的：
如果你的树几乎已满，那就是除了最后两个之外，每个级别都有其完整的子级，那么你有N ^（L-2）和N ^（L-1）个叶子节点之间和N ^（L -1）和N ^ L个节点总数 .
如果你的树没有满，那么知道叶子节点的数量并没有帮助，因为完全不 balancer 的树将有一个叶子节点但是任意多个父节点 .
我想知道你的'每个节点有关N个节点'的说法有多精确 - 如果你知道平均分支因子，也许你可以计算树的预期大小 .
如果您能够找到叶子与内部节点的比率，并且您知道平均子节点数，则可以将其近似为（n * ratio）^ N = n . 这不会给你你的答案，但我想知道如果有一个比我更好的数学的人能找到一种方法将L插入这个等式并给你一些可溶的东西 .
但是，如果您想要精确地知道，您必须迭代树的结构并随时计算节点 .
计算深度为L的节点数量的公式为:(假设有N个根节点）
NL
要计算每个层需要执行此操作的所有节点的数量：
如果只有一个根节点，则从L中减去1并将总节点数加1 .
请注意，如果在一个节点中叶子的数量与平均情况不同，则会对您的数量产生很大影响 . 在树中越往上越具有影响力 .
这是社区维基，所以随时改变我令人讨厌的代数 .
如果除了树的深度之外你什么都不知道，那么计算总大小的唯一选择就是通过计算它们 .