【题目】霍夫曼编码将频繁出现的字符釆用短编码，出现频率较低的字符采用长编码。具体
的操作过程为： i)以每个字符的出现频率作为关键字构建最小优先级队列；ii)取出关键
字最小的两个结点生成子树，根节点的关键字为孩子节点关键字之和，并将根节点插入
到最小优先级队列中，直至得到一颗最优编码树。霍夫曼编码方案是基于( 1 )策略的。
用该方案对包含 a 到 f 6个字符的文件进行编码，文件包含 100000个字符，每个字符的
出现频率(用百分比表示)如下表所示，则与固定长度编码相比，该编码方案节省了( 2 )
存储空间。
1. A.分治 B.贪心 C.动态规划 D.回溯 答案：B
2. A. 21% B. 27% C. 18% D. 36% 答案：A
1、第一问，基于贪心策略，对文本压缩以获得较短的编码。
2、我们根据字符和出现频率画出哈夫曼树（上一篇有讲怎么画）
昨天我纠结在e画在12左边还是右边，因为画在左边的字符对应的二进制数刚好可以算出结
果，但这里我们不是根据编码计算节省存储空间的，而是根据编码的位数，这里就牵扯到等
长编码相关的知识点。
等长编码是一种简单且译码具有唯一性的编码方式，这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。每个字符都有对应的二进制编码，且长度是固定。所以很容易设计，也很方便读写。假设字符集只含有4个字符A，B，C，D，用两位二进制表示的编码分别为00，01，10，11。
而变长编码使得编码长度得到了大幅的缩小，但是多义性，所以如何设计编码很重要，这时我们就要用到哈夫曼编码。
哈夫曼编码(Huffman Coding)，是由麻省理工学院的哈夫曼博所发明，这个编码方式解决了变长编码多义性的问题。
所以我们再回归到题目，在等长编码上，编写6个字符至少需要3位（a：000，b：001，c：
010……），那么等长编码需要 3*100000 =300*1000 存储空间。
而霍夫曼编码需要：18 * 2（这里乘的是编码长度，也就是编码位数）+32 * 2+4 * 4+8 * 4+12
* 3+26 * 2 = 236*1000（这里的 *1000），这里我再看看！
那么节省的空间为（300-236）/ 300 = 21.333...%
答案就为21%
———————————————————————
普通构建哈夫曼树求哈夫曼码的做法我上一篇有讲，
昨天在画哈夫曼图这里卡了好久，因为碰到了根节点和12等于题目中的e=12的情况，
在画在左边还是右边算出结果不同卡住了，现在终于解决啦，和画法没有关系，
编码长度一样就不影响结果。
标签：编码,12,哈夫曼,字符,关键字,长度 From： https://blog.csdn.net/m0_67423784/article/details/141923936