赫夫曼树(最优二叉树)
1、定义
带权路径长度(WPL)最小的二叉树。
2、建立
举例:将7 ,5, 2, 4构建为一棵赫夫曼树。
挑选最小的两个节点出来,分别为2和4,形成树如下:
6
2 4
此时序列变为7 , 5 ,6
再挑选两个最小的节点出来,形成树如下:
11
6 5
2 4
此时序列变为7,11
再挑选两个最小的节点出来,形成树如下:
18
11 7
6 5
2 4
带权路径长度WPL=3*2+3*4+2*5+1*7=6+12+10+7=35
有了上面带权重的二叉树之后,我们就可以进行编码了。我们把二叉树分支中左边的支路编码为0,右边分支表示为1。这样依次遍历这颗二叉树就可以获取得到所有字符的编码了,例如下面这种形式,l的编码是00,w的编码是01。