哈夫曼树构造方法_二叉排序树怎么构造

哈夫曼树构造方法_二叉排序树怎么构造数据结构哈夫曼树哈夫曼树哈夫曼树的定义在许多实际应用中,树中结点常常被赋予一个表示某种意义的数值,称为该结点的权。从树根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积,称为该结点的带权路径长度。树中所有结点的带权路径长度之和称为全树的带权路径长度,

数据结构–哈夫曼树   哈夫曼树   哈夫曼树的定义   在许多实际应用中,树中结点常常被赋予一个表示某种意义的数值,称为该结点的权。从树根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积,称为该结点的带权路径长度。树中所有结点的带权路径长度之和称为全树的带权路径长度,记为:
WPL=\sum_{i=1}^n W_iL_i , Wi 是第i个结点所带的权值,Li 是该结点到根结点的路径长度。   在含有n个带权叶子的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树。   
哈夫曼树构造方法_二叉排序树怎么构造
哈夫曼树构造方法_二叉排序树怎么构造   (a)WPL = 7 x 2 + 5 x 2 + 2 x 2 + 4 x 2 = 36;   (b)WPL = 7 x 3 + 5 x 3 + 2 x 1 + 4 x 2 = 46;   (c)WPL = 7 x 1 + 5 x 2 + 2 x 3 + 4 x 3 = 35;   其中,c中的树的wpl最小,可以验证,它恰好为哈夫曼树。   哈夫曼树的构造   算法描述如下:将这n个结点分别作为n棵仅含有一个结点的二叉树,构成森林F。构造一个新结点,从F中选取两颗树节点权值最小的树作为新结点的左、右子树,并且将新节点的权值置为左、右子树上根结点的权值之和。从F中删除刚选出的两棵树,同时将新得到的树加入到F中。重复步骤2和3,直至F中只剩下一棵树为止。   
哈夫曼树构造方法_二叉排序树怎么构造
哈夫曼树构造方法_二叉排序树怎么构造   从上述构造过程中可以看出哈夫曼树具有如下特点:每个初始结点最终都成为叶结点,且权值越小的节点到根结点的路径长度越大。构造过程中共新建了 n-1 个结点,因此哈夫曼树中的结点总数为 2n – 1。每次构造都选择 2 棵树作为新结点的孩子,因此哈夫曼树中不存在度为 1 的结点。   哈夫曼编码   对应待处理的一个字符串序列,若对每个字符用同样长度的二进制表示,则称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示,则这种方式称为可变长度编码。 可变长编码的特点是对高频率的字符赋以端编码,而对频率较低的字符则以较长的一些的编码,从而可以使字符平均编码长度剪短,起到压缩数据的效果。   若没有一个编码是另一个编码的前缀,则这样的编码为前缀编码。   
哈夫曼树构造方法_二叉排序树怎么构造
哈夫曼树构造方法_二叉排序树怎么构造   构造出的哈夫曼树不唯一,但各哈夫曼树的带权路径长度相同且为最优。   如果觉得本文对你有帮助的话,不妨作者一波,小小的其实对我很重要。更多高质量内容与资料请访问:https://xiuxin.gitbook.io/datastructre/   个人主页:https://xiuxin-666.gitee.io/

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

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

(0)
上一篇 2024年 9月 2日 下午11:10
下一篇 2024年 9月 2日

相关推荐

关注微信