我正在做一种独特的霍夫曼编码形式,并且正在构造一个满的k元(在这种情况下为3元)树(每个节点将有0个或k个子节点),并且我知道它将有多少叶子在我构造它之前。如何根据叶子数计算树中的节点总数?
我知道在完整的二叉树(2-ary)的情况下,其公式为2L-1,其中L是叶数。我想将此原理扩展到k元树的情况。
最佳答案
考虑一下如何证明完整的二叉树的结果,然后您将大致了解如何实现。对于完整的二叉树,假设高度h
,则节点N
的数量为N = 2^{h+1} - 1
为什么?因为第一级具有2^0
节点,所以第二级具有2^1
节点,并且通常k
th一级具有2^{k-1}
节点。将这些加起来得到总共h+1
级别(因此,高度h
)得到
N = 1 + 2 + 2^2 + 2^3 + ... + 2^h = (2^{h+1} - 1) / (2 - 1) = 2^{h+1} - 1
叶子的总数
L
只是最后一级的节点数,所以L = 2^h
。因此,通过替代,我们得到N = 2*L - 1
对于
k
-ary树,除了2
之外,什么都没有改变。所以N = 1 + k + k^2 + k^3 + ... + k^h = (k^{h+1} - 1) / (k - 1)
L = k^h
所以一点代数可以带你走最后一步
N = (k*L - 1) / (k-1)
关于math - 就叶子数而言,完整k元树中的节点总数是多少?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/7842397/