哈夫曼树和哈夫曼编码

发布时间 2023-12-15 11:10:50作者: qingjiawen

 

 

路径:由树中一个结点到另一个结点之间的分支构成。

路径长度:路径上分支的数目。

树的带权路径长度:树中所有叶子结点的路径长度与权重的乘积之和,通常记作WPL。

 

WPL=2*6+2*9+3*2=36

 带权路径长度WPL最小的二叉树称作最优二叉树或赫夫曼树。

 

 

 

设一组权值集合W={2,3,4,5,6},则由该数值集合构造的赫夫曼树中带权路径长度之和为_____45__________

 

{2,3,4,5,6}---》{4,5,5,6}(2+3)---->{5,6,9}(4+5)------>{9,11}(5+6)---->{20}(9+11)

 WPL=2*3+3*3+4*2+5*2+6*2=45