|
|
|
|
|
.路径：由从树中一个节点到另一个节点之间的分支构成两节点之间的路径。
|
|
|
|
|
|
.树的路径长度：从树根到每一个节点的路径长度之和。
|
|
|
|
.节点的带权路径长度：从节点到根之间的路径长度与节点上权的乘积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种字符出现的频率作为权，由此得到的二进制前缀编码为哈夫曼编码。
|
|
|
