|
|
|
|
|
.路径：由从树中一个结点到另一个结点之间的分支构成两结点之间的路径。
|
|
|
|
|
|
.树的路径长度：从树根到每一个结点的路径长度之和。
|
|
|
|
.结点的带权路径长度：从结点到根之间的路径长度与结点上权的乘积WkLk。
|
|
|
|
.树的带权路径长度：树中所有带权叶子结点的路径长度之和。
|
|
|
|
.哈夫曼树：假设有n个数值{W1，W2，…，Wn}，试构造一棵有n个叶子结点的二叉树，结点带权为W1，带权路径长度WPL最小的二叉树称哈夫曼树。
|
|
|
|
对下图给定的两棵二叉树，它们的带权路径长度分别如下。
|
|
|
|
|
|
|
|
（1）WPL=7*2+5*2+2*2+4*2=36。
|
|
|
|
（2）WPL=7*1+5*2+2*3+4*3=35。
|
|
|
|
|
|
|
|
（1）根据给定的n个数值{W1，W2，…，Wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，左右子树均空。
|
|
|
|
（2）在F中选取两棵根结点的数值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的数值为其左右子树上根结点的数值之和。
|
|
|
|
（3）在F中删除这两棵树，同时将新得到的二叉树加入F中。
|
|
|
|
（4）重复步骤（2）、（3），直到F只含一棵树为止。
|
|
|
|
|
|
哈夫曼编码的设计思想是：若要设计长短不等的编码，则必须是任意一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。利用二叉树来设计二进制的前缀编码，设计长度最短的二进制前缀编码，以n种字符出现的频率作为权，由此得到的二进制前缀编码为哈夫曼编码。
|
|
|
