构建度为K的哈夫曼树

1. 首先确定是否需要添加“虚权值”（即0）。对m个权值建立K叉树，若(m-1)%(k-1)=0，则不需要添加0，否则第一次归并时需要有(m-1)%(k-1)+1 个权值归并。

2. 将m个权值看作m棵只有根结点的K叉树集合F={T1,T2…..Tm}。

3. 从F中选择K个权值最小的树作为子树，构成一棵K叉树，K叉树根结点的权值为所选的K个树根结点权值之和，在F中删除这K棵子树，并将新K叉树加入F中。（根结点要和剩余权值比较）

4. 重复（3）的步骤，直到F中只有一棵树。

5. 例如，10个权值构造最优三叉树，(10-1)%(3-1)=1,第一次归并需要(10-1)%(3-1)+1=2 个权值，但是要构造三叉树，所以补上权值为0 的结点，并不影响计算权值之和。

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

权值个数m=10，K=3

1. 第一次归并需要2个权值，即选择0,1,4 归并。

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

3.重复步骤

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

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