哈夫曼树

哈夫曼树的应用

编码

按个替换

解码

从左到右扫描，三位一次查表替换

T（S）太长了，能不能短一些，出现次数多的，编码短一些；出现次数少的，编码长一些。从而，整个编码串的长度短些。

统计各个字符出现次数。、

对每个字符建立一个节点。

每次从集合中挑选两个出现次数最少的节点 把它们从集合中删除，并且将这两个节点构造一个新结点，新结点出现的次数，是这两个被删除节点的次数之和。把这个新节点 并入集合中。

构成了一棵二叉树，给左分支标记上0，给右分支标记上1 。

叶子节点就是之前那些字符所在的节点。

我们这样给字符编码：

从根节点走到叶子节点所经过的分支上的代码组成了叶子节点的编码。

满足刚才的要求：
出现次数多的字符，编码短些。
出现次数长的字符，编码长些。

出现次数较多地字符，其所在的叶子节点距离根节点近些
而出现次数少的字符，其所在的叶子节点距离根节点远些

那怎么解码？

从左往右扫描编码串，每扫描一位，就把它当作路径指示标，按照这一位编码，从根节点开始走一步，然后继续扫描，继续按照编码的指示，继续走。就这样 直到走到了叶子节点。那就解码出叶子节点所在的字符

歧义

如果一个字符的编码 是另一个字符的前缀，那就会出现歧义，

我们是怎么编码的？

从根节点 一直走到 叶子节点 ，这个路径上的分支代码 代表编码。

那有没有可能从根节点沿着一条路径 经过 两个叶子节点？

显然不可能，同样也说明，不可能出现 一个是另一个的前缀。

路径长度 就为3

权值 这里就是 字符出现的次数。

树中没有单分支节点，除了叶子节点之外，每个节点都有左右孩子。
这类树 ，又叫正则二叉树。

哈夫曼三叉树，规则非常类似，只不过把之前的每次选两个最小的节点，变为选三个最小的节点。

对于哈夫曼二叉树，只要给出的节点 多于两个，我们就可以构造。
而对于三叉树/n叉树 就不一样，

这个无法构造

我们需要补上 权值为0 的节点

增加的节点会不会影响 带权路径长度。，
显然不会， 增加的节点权值为0