And*_*rew 30 math tree encoding character-encoding data-structures
我正在做一个独特的霍夫曼编码形式,并且正在构建一个k-ary(在这个特殊情况下,3-ary)树已满(每个节点将有0或k个孩子),我知道它会有多少叶子在我构建它之前.如何根据叶数计算树中的节点总数？
我知道在完整二叉树(2-ary)的情况下,这个公式是2L - 1,其中L是叶子的数量.我想将这个原则扩展到k-ary树的情况.
Pen*_*One 38
考虑如何证明完整二叉树的结果,您将看到如何一般地完成它.对于完整的二叉树,比如高度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棵树,没有任何变化,但是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)