哈夫曼树的数据结构_哈夫曼树只有度为0和度为2

哈夫曼树的数据结构_哈夫曼树只有度为0和度为2【数据结构】哈夫曼树及哈夫曼编码实现1. 哈夫曼树1.1 基本概念路径:指从根结点到该结点的分支序列。路径长度:指根结点到该结点所经过的分支数目。结点的带权路径长度:从树根到某一结点的路径长度与该结点

【数据结构】哈夫曼树及哈夫曼编码实现   1. 哈夫曼树   1.1 基本概念   路径:指从根结点到该结点的分支序列。   路径长度:指根结点到该结点所经过的分支数目。   结点的带权路径长度:从树根到某一结点的路径长度与该结点的权的乘积。   树的带权路径长度(WPL):树中从根到所有叶子结点的各个带权路径长度之和。   哈夫曼树是由 n 个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树,又称最优二叉树。如图中第三棵树就是一棵哈夫曼树。   
在这里插入图片描述   1.2 构造哈夫曼树   构造哈夫曼树的算法步骤:   ① 初始化:用给定的 n 个权值{w1,w2,…,wn}构造 n 棵二叉树并构成的森林F={T1,T2,…,Tn},其中每一棵二叉树Ti(1<=i<=n)都只有一个权值为 wi 的根结点,其左、右子树为空。   ② 找最小树:在森林 F 中选择两棵根结点权值最小的二叉树,作为一棵新二叉树的左、右子树,标记新二叉树的根结点权值为其左、右子树的根结点权值之和。   ③ 删除与加入:从 F 中删除被选中的那两棵二叉树,同时把新构成的二叉树加入到森林 F 中。   ④ 判断:重复②、③操作,直到森林中只含有一棵二叉树为止,此时得到的这棵二叉树就是哈夫曼树。   简单的说就是先选择权小的,所以权小的结点被放置在树的较深层,而权较大的离根较近,这样一来所构成的哈夫曼树就具有最小带权路径长度。   例如给定5个权值{2,3,5,7,8},构造过程如下:   
在这里插入图片描述   注意:由于未规定左右子树顺序,因此哈夫曼树不唯一,但树的最小带权路径长度唯一。如下图两棵树都是根据5个权值{2,3,5,7,8}构造的哈夫曼树:   1.3 哈夫曼树的类型定义   哈夫曼树是一种二叉树,其中没有度为1的结点,因此一棵有 n 个叶子的哈夫曼树共有 2n-1 个结点,可以用一个大小为 2n-1 的一维数组来存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息,所以构成一个静态三叉链表。   
在这里插入图片描述   1.4 哈夫曼树创建的算法实现   基于上文中的构造哈夫曼树的步骤,代码如下:   2. 哈夫曼编码实现   2.1 哈夫曼编码   对一棵具有n个叶子结点的哈夫曼树,若对树中的每个左分支赋0,右分支赋1(或左1右0),则从根到每个叶子的通路上,各个分支的赋值分别构成一个二进制串,该二进制串就称为哈夫曼编码。哈夫曼编码是最优前缀编码,能使各种报文对应的二进制串的平均长度最短。   例如要传送数据“state,seat,act,tea,cat,set,a,eat”,先统计各个字符出现的次数:   字符 c s e a t   字符出现的次数 2 3 5 7 8   将出现次数当作权构造哈夫曼树,并按左0右1规则对分支赋值:   
在这里插入图片描述   则各字符的哈夫曼编码为:   字符 c s e a t   字符出现的次数 2 3 5 7 8   哈夫曼编码 010 011 00 10 11   可以看出使用频率越高的字符编码长度越短。

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/76142.html

(0)
上一篇 2024年 8月 4日 下午3:14
下一篇 2024年 8月 4日 下午3:18

相关推荐

关注微信