[数据结构] 树和二叉树-哈夫曼树和哈夫曼编码

几个概念

路径长度

两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是各叶结点到根节点的路径长度之和。

路径长度最小值

带权路径长度

树的带权路径长度是树的各叶子结点所带的权值与该结点到根的路径长度的乘积的和

几种不同WPL的二叉树

第一个：WPL=2*2+4*2+5*2+7*2=2（2+4+5+7）=36

第二个：WPL=2*1+4*2+5*3+7*3=46

第三个：WPL=7*1+5*2+2*3+4*3=35

哈夫曼树

概念

带权路径长度最小的二叉树就是哈夫曼树。在哈夫曼树中，权值大的结点离根最近。

哈夫曼算法

哈夫曼树的构造

几点说明：

• 在初始序列【7,5,2,4】排序，即【2,4,5,7】。
• 选两个最小的，作为叶子结点画出来，和是6，然后用6代替这俩结点，即【6,5,7】。
• 再排序，即【5,6,7】，在选两个最小的重复上面的过程。
• 此外，哈夫曼树左右子树可以交换，但是一般来说小的在左边，所以哈夫曼树不唯一，但是WPL都是最小的。

例题