文章总数60祭+哈夫曼树（NOIP普及组初赛冲刺L2）

**文章总数60祭+哈夫曼树（NOIP普及组初赛冲刺L2）** 讲讲如何构建哈夫曼树 （敲黑板） **考点1：运用的思想** 贪心（有一定递归） reson1:没有比较就没有伤害 比较了还不是贪心？ reson2：排序贪心一家亲 从小到大排了序，还不是贪心？ 也有递归（从下往上建树） **考点2：建树** 发个例题~ 2011年noip普及组初赛真题 现有一段文言文，要通过二进制哈夫曼编码进行压缩。假设这段文言文只由4个汉字“之”“乎”“者”“也”组成，它们出现的次数分别为700、600、300、200。那么，“也”字的编码长度是（ ） A. 1 B. 2 C. 3 D. 4 答案：C 为什么？ 看看小蛤蛤怎么建树的： step1:排序（小->大） step2:选1、2小，左一右二 step3:算和，做父亲，标灰 step4:选当前最小，大于父亲右边，小与左边 (重复step3,4) 建出来的树： 看不到而~ 见desktop->picture->dalao6 接着计算。 判断所在节点的深度。（根节点为0） 所求即为答案。 放个犇犇 汉字 概率 编码 之： 700 00 乎： 600 011 者： 300 0101 也： 200 0100 (编码数如图这个二叉树得到，左边为0，右边为1，每一个字符都从根节点数) 可以看出：出现次数越多的字符，编码越短；出现次数越少的字符，编码越长。这样就能让编码后的文件大小能够最短。 还有2天，加油！ OQLYE JR.™