Question

n个叶子结点的哈夫曼树共有几个分支节点？

分支结点

Answer 1

二叉树的节点数是不确定的，与权数有关，但有一个最小值。哈夫曼树是带权的，常用的权值是访问频率。每个叶子的访问路径长度（树的层数）乘以权值之和最小的二叉树，就是哈夫曼树。最大叶子数与层数的关系是（完全树为基础）：
1，2，4，8，..，2^(k),k为层号，从0（根）开始。
2^k=n,k=log2(n)的整数。
如果存在整数k，2^k=n,则：
节点数=1+2+4+8+...+2^(k-1)+2^k
=2^(k+1)-1,
其中分支节点数（非叶）2^k-1，
如果不存在整数k，2^k=n,则，但是，存在k，2^k<n<2^(k+1)
将k层在一些叶子，n-2^k个，改为分支节点，叶子数加倍。得到n个叶子。
分支节点数2^（k+1）-1+n-2^k=2^k+n-1个。
n层，每层一个叶子，路径最大。分支节点n个。