文章图片
哈夫曼树（最优树）及其应用 路径长度的概念
1.路径：从一个结点到另一个结点之间的分支序列
2.结点之间的路径长度：从一个结点到另一个结点之间的分支数目
3.树的路径长度（用PL表示）：从树的根到每一个结点的路径长度之和 - - ->深度之和
文章图片
PL = 0＋1＋1＋2＋2＋2＋2＋3＝13
文章图片
PL = 0＋1＋1＋2＋2＋3＋3＋3＝15
结点的权：
给树的每个结点赋予的一个具有某种实际意义的实数。
结点的带权路径长度：
从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度：
树的所有叶结点的带权路径长度之和
文章图片
WPL=7*2+5*2+2*2+4*2=36
树的带权路径长度记作：
文章图片
其中：Wi为树中每个叶子结点的权，L i为每个叶子结点到根的路径长度
文章图片
WPL最小的二叉树就称作最优二叉树或哈夫曼树
哈夫曼树
带权路径长度达到最小的扩充二叉树即为哈夫曼树。哈夫曼树中，权值大的结点离根最近。
哈夫曼树的应用
(1)前缀码：如果在一个编码系统中，任一个编码都不是其他任何编码的前缀（最左子串），则称该编码系统中的编码是前缀码。例如，一组编码01，001，010，100，110就不是前缀码，因为01是010的前缀，若去掉01或010就是前缀码。例如，名字中的郑霞、郑霞锦就不是前缀码。
(2)哈夫曼编码：对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，该二进制串就称为哈夫曼编码。
(3)哈夫曼编码主要用于压缩、解缩
哈夫曼树的构建 通过单词出现的次数构建哈夫曼树
原有数据(单词出现的次数)：7 5 2 4
每次从原有数据中挑两个最小的，小的放左边，大的放右边：挑出 2 和 4，构建新节点 6，再把新数据 6 丢到原有数据中，再挑两个最小的出来...从而构建哈夫曼树
【数据结构|数据结构 --- 哈夫曼树基础】哈夫曼编码：往左边走是0，往右边走是1
用堆的实现，小顶堆：每次从原有数据中拿两个最小的，贪心算法的思想
文章图片
a 字符存储占用一个字节，现在内存中用 0 表示即可
a b c d d d - -> 原来存储占用 6个字节
用二进制去存储所需要的内存：0 10 110 111 111 111，二进制中8位表示一个字节，用 2 个字节就可以完全存储，因此可以用来做压缩，哈夫曼树主要用于做字符串的编码
01 和 0 不能同时存在，假设 0 表示 a，01 表示 b，做拆分时不能做区分是指 a 还是 b：在一个编码系统中，任一个编码都不是其他任何编码的前缀
编码表：a：0，b：10，c：110，d：111
还原字符串：010110111111111，找字符0，01在编码中不存在，因此可以把0拆分开来...101 在编码中不存在，因此，可以拆分出10...
推荐阅读
- 数据结构与算法|【干货】数据结构与算法该如何正确学习（（书籍\视频\网站都推荐了））
- C语言进阶|【详解C语言指针】我真的让C指针给我唱征服了~乌拉
- 笔记|第十二届蓝桥杯——Java软件开发（省赛）（括号序列（笔记15））
- 面试|面试官（看到你熟练性能调优，可以说一下你对MySQL索引的理解（））
- 算法竞赛|【算法入门到进阶】【学习目录】
- C++|c++中string的模拟实现
- Python数据结构与算法|Python数据结构与算法（3.1）——栈
- java之数据结构|JAVA数据结构之集合
- 数据结构和算法|数据结构和算法