用途：哈夫曼树用于求解树的最小带权路径；哈夫曼编码由哈夫曼树演变而来，用于设计最优可变长编码。

　　注：带权路径：根到叶子结点的距离与叶子结点权值的乘积；最小带权路径：树中根到所有叶子结点的带权路径之和的最小值。

 

思想：贪心

 

算法描述：

　　1、树由一颗m叉树构成，由讨论的n个元素构成树的叶子节点。（m>=2）

　　2、确保 n=k(m-1)+1，其中k>=0.当n不满足条件时，添加权值为0的虚拟节点使其满足条件，辅助构造m叉树。

　　3、以n个元素为初始序列，每次选择权值最小的m个元素，并在序列中删除；使m个元素共同连接到同一个父结点上，该父结点权值为所有叶子结点权值之和；将父结点添加到序列中。

　　4、重复上述操作，直到序列中元素个数为1，该元素作为根。

版权声明：本文为xinwang-coding原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/xinwang-coding/p/13980050.html