树数据结构中的节点总数？ [英] Total number of nodes in a tree data structure?

问题描述

我有一个树状数据结构，L级深，每个节点都有关于 N个节点。我想要计算树中总共的节点数。要做到这一点（我想），我需要知道有多少个节点将有孩子。

这个比例的叶节点与非N中的叶节点

在三个中编出总数节点的公式是什么？

更新有人在其中一个答案中提到了分支因素，但它却消失了。我认为这是我正在寻找的这个词。那么公式是否应该考虑分支因素？

更新我应该对假设的数据结构进行估计，而不是确切的

解决方案

好的，每个节点都有N个子节点，树是L级深层。

 具有1级，树有1个节点。 
有2个级别，树有1 + N个节点。 
有3个级别，树有1 + N + N ^ 2个节点。 
具有L级，树具有1 + N + N ^ 2 + ... + N ^（L-1）个节点。 
  

节点总数为（N ^ L-1）/（N-1） / p>

好的，只是一个小例子，为什么，它是指数的：

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

I have a tree data structure that is L levels deep each node has about N nodes. I want to work-out the total number of nodes in the tree. To do this (I think) I need to know what percentage of the nodes that will have children.

What is the correct term for this ratio of leaf nodes to non-leaf nodes in N?

What is the formula for working out the total number nodes in the three?

Update Someone mention Branching factor in one of the answer but it then disappeared. I think this was the term I was looking for. So shouldn't a formula take the branching factor into account?

Update I should have said an estimate about a hypothetical datastructure, not the exact figure!

解决方案

Ok, each node has about N subnodes and the tree is L levels deep.

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.

The total number of nodes is (N^L-1) / (N-1).

Ok, just a small example why, it is exponential:

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

这篇关于树数据结构中的节点总数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！