霍夫曼树

霍夫曼树

在数据结构与算法中，人们把最小带权路径长度的二叉树称为霍夫曼树或者最优二叉树。

霍夫曼算法

对应于霍夫曼树的算法也叫做霍夫曼算法。此算法的思想是：

（1）设给定的一组权值为{W1，W2，W3，……Wn}，据此生成森林F={T1，T2，T3，……Tn},F 中的每棵二叉树只有一个带权为W1的根节点（i=1，2，……n）。

（2）在F中选取两棵根节点的权值最小和次小的二叉树作为左右构造一棵新的二叉树，新二叉树根节点的权值为其左、右子树根节点的权值之和。

（3）在F中删除这两棵最小和次小的二叉树，同时将新生成的二叉树并入森林中。

（4）重复（2）（3）过程直到F中只有一棵二叉树为止。

霍夫曼树的应用非常广，在不同的应用中叶子节点的权值可以作不同的解释。霍夫曼树应用于信息编码中，权值可以看成某个符号出现的频率；应用到判定过程中，权值可以看成某类数据出现的频率；应用到排序过程中，权值可以看成是已排好次序而等待合并的序列长度等。