算法与数据结构--哈夫曼树与哈夫曼编码

2023-12-21 19:55:59

演示视频:
【1】数据结构——五分钟搞定哈夫曼树,会求WPL值,不会你打我_哔哩哔哩_bilibili
【2】哈夫曼树和哈夫曼编码_哔哩哔哩_bilibili
【3】哈夫曼树的构造的做题三步骤_哔哩哔哩_bilibili

求哈夫曼编码的步骤:
1.根据字符及其权值(权值一般是数出现的次数)构造出哈夫曼树
2.根据建立好的哈夫曼树求出哈夫曼编码。

每个结点包括数据本身及其权值(及该数据出现的次数)

一.怎样构造哈夫曼树

1.将这串数据塞进优先队列,该优先队列中的数据按照数据的出现次数(或者说权值)从小到大进行排序。
将这些元素看成是只有根节点二叉树的根结点,相当于构造n棵只有根节点的二叉树。
2.选取权值最小的两个节点,将这两个结点对应的树作为左右子树,并创建一个新的父节点,从而构造一个新的二叉树。新节点的权值为这两个节点的权值之和。
3.将这两个最小的子结点出队,新创建的结点入队。【即:在森林中删除这两棵树,同时将新得到的二叉树加入森林中】
4.重复2,3步骤,直到节点集合中只剩下一个节点(只含一棵树),即哈夫曼树的根节点,对应的树即为哈夫曼树。哈夫曼树就构建完成了。
具体演示见视频。

二.根据哈夫曼树求出哈夫曼编码

什么是哈夫曼编码?

根据上面的定义,我们就很容易根据哈夫曼树求出每个数的哈夫曼编码。

三.计算WPL值(带权路径长度)

将最开始优先队列的每个数的权值乘以其所在的层数相加。【注意根结点在第0层,从第0层开始计算】

文章来源:https://blog.csdn.net/bjjx123456/article/details/134465647
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。