二叉树(五)——哈夫曼树与哈夫曼编码
基本概念
WPL(树的带权路径长度)
若给具有m个叶结点的二叉树的每个叶结点赋予一个权值,则该二叉树的带权路径长度定义为:
其中,wi为第i个叶结点被赋予的权值,li为第i个叶结点的路径长度;
例子如下:
哈夫曼树的定义
给定一组权值,构造出的具有最小带权路径长度的二叉树称为哈夫曼树,如下:
哈夫曼树的特点
哈夫曼树具有如下特点:
1、权值越大的叶结点离根结点越近,权值越小的叶结点离根结点越远;(这样的二叉树WPL最小)
2、无度为1的结点;
3、哈夫曼树不是惟一的。
哈夫曼树的构造
哈夫曼树构造的核心思想如下:
1、对于给定的权值W={w1,w2,…, wm},构造出树林F={T1,T2,…, Tm},其中,Ti(1≤i≤m)为左、右子树为空,且根结点(叶结点)的权值为wi的二叉树;
2、将F中根结点权值最小的两棵二叉树合并成为一棵新的二叉树,即把这两棵二叉树分别作为新的二叉树的左、右子树,并令新的二叉树的根结点权值为这两棵二叉树的根结点的权值之和,将新的二叉树加入F的同时从F中删除这两棵二叉树;
3、重复步骤2,直到F中只有一棵二叉树。
例子如下: