哈夫曼树和哈夫曼编码

  在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。

哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

  哈夫曼编码步骤

    • 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列。)
    • 二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和
    • 三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中
    • 四、重复二和三两步,直到集合F中只有一棵二叉树为止。

  eg:对于这样的8个节点:5  29  7  8  14  23  3  11,我们进行哈夫曼编码的过程如下:








Huffman 编码树

  例:D={A,B…, M}     W={2,3,5,7,11,13,17,19,23,29,31,37,41},则对应的哈夫曼树如下:

  然后,我们利用Huffman算法构造出的各字符的二进制编码为(节点的左子树编码为0,右子树编码为1):

A: 1011110 B: 1011111 C: 101110 D: 10110   E: 0100 F: 0101 G: 1010 H: 000   I: 001 J: 011 K: 100 L2: 110  M: 111

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据和云计算技术

算法基础8:平衡树之红黑树

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第8篇《平衡查找树概述》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法...

3465
来自专栏算法channel

基本算法|图解各种树(三)

01 AVL树 二叉树,可以退化到单链,也可以满二叉树,用到二叉树时编码的方便,常常虚拟出一种真二叉树,还说到了一种特列(二叉树)来描述多叉树的方法。 基本算...

3715
来自专栏xingoo, 一个梦想做发明家的程序员

AVL树

详细描述,好像跟我自己写的差不多......不过终究是大神级别,讲的就是透彻 1. 概述 AVL树是最早提出的自平衡二叉树,在AVL树中任何节点的两个子树的高度...

2688
来自专栏吴伟祥

【数据结构】务实篇 原

                                                             还有非线性结构(树、图等)。

833
来自专栏向治洪

算法之红黑树

红黑树(一) 原理和算法详细介 1 R-B Tree简介     R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树...

2536
来自专栏趣学算法

数据结构 第17讲 沟通无限校园网——最小生成树(kruskal算法)

构造最小生成树还有一种算法,Kruskal算法:设G=(V,E)是无向连通带权图,V={1,2,…,n};设最小生成树T=(V,TE),该树的初始状态为只有n...

1742
来自专栏Vamei实验室

纸上谈兵: AVL树

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢! 二叉搜索树的深度与搜索效率 我们在树, 二...

2346
来自专栏Golang语言社区

AVL二叉树

AVL二叉查找树 AVL二叉查找树是一种特殊的二叉查找树,其规定 每个节点的左子树和右子树的高度差最多是1 AVL调整算法 AVL树插入一个新的节点到某个节点下...

32310
来自专栏Android相关

红黑树(Red-Black Tree)

红黑树,本质上来说就是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(...

2053
来自专栏上善若水

058 关于二叉树 红黑树 B树等

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常...

2033

扫码关注云+社区

领取腾讯云代金券