|
|
|
霍夫曼树又称最优二叉树，是一类带权路径长度最短的树。
|
|
|
|
路径：是指从树中一个节点到另一个节点之间的通路，路径上的分支数目称为路径长度。
|
|
|
|
树的路径长度：是从树根到每一个叶子的路径长度之和。节点的带权路径长度为从该节点到树根之间的路径长度与该节点权的乘积。
|
|
|
|
树的带权路径长度：指树中所有叶子节点的带权路径长度之和，记为
|
|
|
|
|
|
式中，n为带权叶子节点的数目；wi为叶子节点的权值；li为叶子节点到根的路径长度。
|
|
|
|
霍夫曼树是指权值为w1，w2，…，wn的n个叶子节点的二叉树中带权路径长度最小的二叉树。
|
|
|
|
|
|
（1）根据给定的n个权值w1，w2，…，Wn构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树均空。
|
|
|
|
（2）在F中选取两棵根节点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根节点的权值为其左、右子树根节点的权值之和。
|
|
|
|
（3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。
|
|
|
|
重复（2）、（3），直到F中只含一棵树时为止。这棵树便是霍夫曼树。
|
|
|
