我正在做一种独特的霍夫曼编码形式,并且正在构造一个满的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/

10-11 22:51
查看更多