构建度为K的哈夫曼树

首先确定是否需要添加“虚权值”（即0）。对m个权值建立K叉树，若(m-1)%(k-1)=0，则不需要添加0，否则第一次归并时需要有(m-1)%(k-1)+1 个权值归并。
将m个权值看作m棵只有根结点的K叉树集合F={T1,T2…..Tm}。
从F中选择K个权值最小的树作为子树，构成一棵K叉树，K叉树根结点的权值为所选的K个树根结点权值之和，在F中删除这K棵子树，并将新K叉树加入F中。（根结点要和剩余权值比较）
重复（3）的步骤，直到F中只有一棵树。
例如，10个权值构造最优三叉树，(10-1)%(3-1)=1,第一次归并需要(10-1)%(3-1)+1=2 个权值，但是要构造三叉树，所以补上权值为0 的结点，并不影响计算权值之和。

[!NOTE]

构造哈夫曼树的思想是每次选取K个权重最小的元素来合成一个新元素，该元素权重为K 个元素权重之和。但是当K大于2时，按照这个步骤做下去可能到最后剩下的元素个数少于K个。解决这个问题的办法就是，假设已经有了一棵度为K的哈夫曼树（满K叉树），则可以预先知道其叶节点数为 $(K-1)N_K+1$，$N_K$表示度为K的结点数目。于是，对于给定的m个权值构造K叉哈夫曼树，可以考虑增加一些权值为0 的叶子结点，使得叶子总数为 $(K-1)N_K+1$，然后再构造。

例如：1,4,9,16,25,36,49,64,81,100 构造最优三叉树

权值个数m=10，K=3

2.根结点权值为5，并入集合当中，继续选择3个最小权值即5,9,16

3.重复步骤

4.当权值91 并入集合中时，下一次选择最小的3个取值为49,64,81，构成一棵子树，根结点为权值之和194

5.最终集合中剩余的取值为91,100,194，最优三叉树的最终形态

Dase/算法