一个完整的k-ary树中的节点总数是多少？ [英] 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个子节点），我知道有多少叶子它将有我之前我构建它。如何根据树叶数计算树中的节点总数？

我知道在一个完整的二叉树（2-ary ），其公式为2L-1，其中L是叶数。

解决方案

想想如何证明结果一个完整的二叉树，你会看到如何做到一般。对于完整的二叉树，例如高度 h ，节点数量 N 是

N = 2 ^ {h + 1} - 1

因为第一级具有 2 ^ 0 节点，第二级具有 2 ^ 1 节点， k 级具有 2 ^ {k-1} 个节点。将这些总共添加到 h + 1 级别（因此高度 h ）会产生

  N = 1 + 2 + 2 ^ 2 + 2 ^ 3 + ... + 2 ^ h =（2 ^ {h + 1} /（2  -  1）= 2 ^ {h + 1}  -  1 
  

L 只是最后一级的节点数，因此 L = 2 ^ h 。因此，通过替换，我们得到

  N = 2 * L  -  1 
  / pre> 
 
 
对于 k  code>。 
  N = 1 + k + k ^ 2 + k ^ 3 + ... + k ^ h = {h + 1}  -  1）/（k-1）
 
 L = k ^ h 
  
 
 b $ b 
因此有点代数可以带你最后一步获得
  N = -  1）/（k-1）
  
 
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?

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.
解决方案
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

Why? Because the first level has 2^0 nodes, the second level has 2^1 nodes, and, in general, the kth 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
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
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-ary树中的节点总数是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！