哈夫曼树是满二叉树吗？我就奇怪了，书上的图都不是满二叉树，怎么就有那么多人回答是满二叉树呢，

设给定权值总数有n 个，其哈夫曼树的结点总数为
的答案为什么有人说是满二叉树，答案是2n-1，可是有的题上的答案是不确定呢，到底是不是满二叉树？？？

chiconysun · 2018-4-30 01:54:40

不是满二叉树，是正则二叉树（也叫正规二叉树），其中只有度为0和度为2的结点
因为n0 = n2 + 1，所以n个叶子的正则二叉树自然只有2n-1个结点
至于满二叉树当然也是正则二叉树的特例

1 个回复