大话数据结构-树(12) _前序遍历

(3) 使结点N1的权值为其左右结点权值之和，即1+3=4 ，把FX中的C和F ，取出，并放入N1 ，此时FX={N1-4, B-5, D-4, E-5, G-6, H-7, I-9, J-6}；
(4) 再建一个只有根结点N2的树，然后令FX中，权值最小的结点为N2的左结点，权值第二小的结点为N2的右结点，如下所示：
(5) 调整FX ，令N2的权值为其左右结点权值之和，并替换原FX中的N1和D ，得到新的FX={N2-8, B-5, E-5, G-6, H-7, I-9, J-6}；
(6) 重复以上步骤，直到FX中没有结点，得到以下二叉树：
(7) 把临时加的结点，即N1、N2…的权值去掉，得到赫夫曼树：
此时，树的带权路径长度为151 。
这里出现问题：为什么比上文用到的二叉树：
的带权路径长度长呢？难道构造出来的不是赫夫曼树？
原因是因为，赫夫曼树的主要应用场景，是“不同判断逻辑使用不同处理方式” ，也即，上图只是用来说明什么是路径长度，什么是带权路径长度，如果要适用“不同判断逻辑使用不同处理方式” ，上图应变更成：
其带权路径长度是194 。
7.7.3 赫夫曼编码
赫夫曼研究这种最优树的目的是为了解决当年远距离通信（主要是电报）的数据传输的最优化问题。
比如我们有一段文字内容为“”要网络传输给别人，显然用二进制的数字（0和1）来表示是很自然的想法，这段文字有六个字母，转化为二进制是：
字母
二进制
000
001
010
011
100
101
于是传输的数据变为“” ，对方接收时，可以按每三位分一份来进行解析。
如果一篇文章很长的话，这样的二进制数据将会非常长，但实际上，无论是中文还是英文的文章，字母和汉字出现的频率是不同的，我们可以按照频率，进行赫夫曼树进行规划。
如字符串“” ，我们计算出每个字母出现的比例，再把比例乘以100 ，得到每个字母出现的权值：A-20、B-10、C-10、D-30、E-20、F-10 ，按照赫夫曼树构造方法，构造出如下赫夫曼树：
我们将赫夫曼树的权值左分支改为0 ，右分支改为1：
然后我们将这六个字母从树根到叶子所经过路径的0或1来编码，得到新的编码：
字母
编码
00
1010
1011
11
01
100
那么，传输的数据就产生变化了，以下是赫夫曼优化后前后的数据编码：
二进制串
字符长度
优化前
30
优化后
111
25
也就是说，我们传输的数据被压缩了，节约了大约17%的存储或传输成本，随着字符的增加和多字符权重的不同，这种压缩会更加显出其优势。
将字符按出现频率作为权值构建赫夫曼树，然后设置赫夫曼树的左分支权值为0 ，右分支权值为1 ，从根结点到子结点所经过的路径分支组成0和1的序列为子结点的编码，这就是所谓的“赫夫曼编码” 。
在生成赫夫曼编码时，应注意，任一字符的编码不能是另一个字符的编码的前缀，例如，若有字符的编码是1010 ，则其他字符的编码不能是1、10、101 ，当然也不可能会是1010 。