在学习时，李春葆数据结构一书给出定义，在...二叉树中，WPL最小的二叉树称为哈夫曼树。该点很容易导致我们认为哈夫曼树只能是二叉树。但在刷题过程中，天勤一书写到哈夫曼树不一定是二叉树，有可能是多叉树。
百度百科给出解释：
哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为(k-1)nk+1,式子中的nk表示子节点数目为k的节点数目。于是对给定的n个权值构造k叉哈夫曼树时,可以先考虑增加一些权值为0的叶子节点，使得叶子节点总数为(k-1)nk+1这种形式,然后再按照哈夫曼树的方法进行构造即可。
因此书上定义在做题时会造成思想上的误差。
题目：若一颗度为m的哈夫曼树有n个叶子结点，则非叶子结点个数为：
A. n-1
B. [n/m]-1
C. [n-1/m-1]
D. [n/m-1]-1
一般解决该类题型我们只需要举简单例子代入看是否符合条件即可，但如果是二叉树的情况下，会发现A和C两个选项是一致的，因为二叉树度m=2恒定。
因此本题只能自行推导，设度为m的结点有nm个，度为0的结点有n个，总结点数为N，N=nm+n。又因为有N个结点的哈夫曼树有N-1条分支，则m×nm=N-1=nm+n-1，整理只有C选项成立。
说明：哈夫曼树不一定是二叉树，有可能是多叉树
原文：https://www.cnblogs.com/wangzheming35/p/13283180.html