若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为()哈夫曼树不是最优二叉树,那每个结点度数要么是0,1或2,那这道题目怎么会说“度数为m”的哈夫曼树呢?

Question

若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为()
哈夫曼树不是最优二叉树,那每个结点度数要么是0,1或2,那这道题目怎么会说“度数为m”的哈夫曼树呢?

Answer 1

首先说明一点,我们平时一般所说的哈夫曼树是指最优二叉树,也叫做严格二叉树（注意不是完全二叉树）,但是哈夫曼树完全不局限于二叉树,也存在于多叉树中,即度为m的哈夫曼树,也叫最优m叉树,严格m叉树（注意不是完全m叉树）.
这种最优m叉树在数据结构中也有应用,比如外部排序中的置换-选择排序法.这种树的典型特点是只有度为0和度为m这两种情况,不存在度大于0,小于m的情况,而我们一般最常接触的就是给你一组数据,让你构造最优m叉树.
但是与最优二叉树不同的是,给你的一组数据不一定恰好能构造出最优m叉树,原因是假设度为0的结点个数为x（也就是叶子结点）,度为m的结点个数为y,则存在一个等式x+y=my+1,也就是说x-1能被m-1整除,但是给出你的数据个数（也就是x）不一定能整除啊,怎么办呢?
第一,我们要计算(x-1)%(m-1)是否为0,若为0自然好说,直接构造最优m叉树,若不为0,则需要一些工作了；
第二,假设(x-1)%(m-1)不等于0,怎么办呢?需要给这组数据添上一些数据使其能够整除.添哪些数据呢?又要添几个呢?为了不影响树的构造过程,我们只能够添0,但是添几个合适呢?根据除数m-1和余数,我们不难得到,所添0的个数应为除数和余数的差.这样我们就能够保证总能够构造出最优m叉树.
第三,接下来就需要根据构造最优二叉树的方法来构造最优m叉树,每次选取m个数据,求和后再放入原数据组中（删除那m个数据）,继续这一步骤,直到只剩一个数据（根结点）.