就叶子数而言,完整 k 叉树中的节点总数是多少? [英] What is the total number of nodes in a full k-ary tree, in terms of the number of leaves?
问题描述
我正在做一种独特形式的 Huffman 编码,并且正在构建一个完整的 k-ary(在这种特殊情况下,3-ary)树(每个节点将有 0 或 k 个孩子),我知道有多少在我建造它之前它就会有.如何根据叶子数计算树中的节点总数?
I am doing a unique form of Huffman encoding, and am constructing a k-ary (in this particular case, 3-ary) tree that is full (every node will have 0 or k children), and I know how many leaves it will have before I construct it. How do I calculate the total number of nodes in the tree in terms of the number of leaves?
我知道在完全二叉树(2-ary)的情况下,这个公式是 2L - 1,其中 L 是叶子的数量.我想将此原则扩展到 k 叉树的情况.
I know that in the case of a full binary tree (2-ary), the formula for this is 2L - 1, where L is the number of leaves. I would like to extend this principle to the case of a k-ary tree.
推荐答案
想想如何证明一棵完整二叉树的结果,你会看到一般的做法.对于全二叉树来说,高度h
,节点数N
是
Think about how to prove the result for a full binary tree, and you'll see how to do it in general. For the full binary tree, say of height h
, the number of nodes N
is
N = 2^{h+1} - 1
为什么?因为第一层有2^0
个节点,第二层有2^1
个节点,一般来说,k
层有2^{k-1}
个节点.将这些加起来总共 h+1
个级别(所以高度 h
)给出
Why? Because the first level has 2^0
nodes, the second level has 2^1
nodes, and, in general, the k
th level has 2^{k-1}
nodes. Adding these up for a total of h+1
levels (so height h
) gives
N = 1 + 2 + 2^2 + 2^3 + ... + 2^h = (2^{h+1} - 1) / (2 - 1) = 2^{h+1} - 1
叶子总数L
就是最后一层的节点数,所以L = 2^h
.因此,通过替换,我们得到
The total number of leaves L
is just the number of nodes at the last level, so L = 2^h
. Therefore, by substitution, we get
N = 2*L - 1
对于 k
-ary 树,除了 2
没有任何变化.所以
For a k
-ary tree, nothing changes but the 2
. So
N = 1 + k + k^2 + k^3 + ... + k^h = (k^{h+1} - 1) / (k - 1)
L = k^h
所以一点代数可以带你完成最后一步
and so a bit of algebra can take you the final step to get
N = (k*L - 1) / (k-1)
这篇关于就叶子数而言,完整 k 叉树中的节点总数是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!