🏷️ 基于树的编码

给文字里的每个字编一串「0 和 1」的秘密号码，就是编码。哈夫曼编码让常出现的字号码最短，把文章压得小小的；格雷编码让相邻两个数字的号码只差一位，让机器转盘读得更准。

考纲知识点：格雷编码
哈夫曼编码

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 六级

(3)理解哈夫曼编码、格雷编码相关原理并能进行简单应用。

📚

先学一学

花 5 分钟读完下面 5 课，再去闯关就不慌啦

📻 编码：给每个符号发一张「0/1 号码牌」

电脑只听得懂 0 和 1。想让电脑认字，就得给每个字编一串号码，这叫编码。最简单的办法是每个字都用一样长的号码，比如 4 位：A=0000、B=0001、C=0010……号码清清楚楚，但有点浪费——因为有些字天天见，有些字几乎不出现，给它们发一样长的号码不划算。

✉️ 生活类比：快递柜钥匙

小区快递柜给每个格子配一把钥匙。天天收快递的你配一把普通钥匙，一年只收一次的叔叔也配一把普通钥匙——其实可以给叔叔一个难开的密码锁，把好用的钥匙留给常客。编码也是这个道理：常出现的符号配短码，就能省下好多位。

💡 口诀：编码就是发号码牌；给常客短牌、给稀客长牌，最省地方。

🌳 哈夫曼编码：跟着上节课的哈夫曼树发短码

上一页学的哈夫曼树在这里派上用场！把字符按出现次数建成哈夫曼树，然后从根出发：往左走记 0，往右走记 1，走到哪个字符，一路上记下的 0/1 就是它的号码。出现多的字符住得离根近，号码就短。

🔢 举个例子：A 出现 5 次、B 出现 2 次、C 和 D 各 1 次

先合并最轻的 C、D，再一层层往上并，最后沿树发码，可能得到：

A → 0（最短，因为它出现最多）
B → 10
C → 110
D → 111（最长，因为它出现最少）

四个字符原来用固定 2 位码要 2×4=8 位/组；现在按频率算平均码长，A 用 1 位最多，整体更省——文章越长省得越多。

💡 口诀：谁出现多谁码短；哈夫曼树沿边走，左 0 右 1 出号码。

🛡️ 前缀码：为什么收到 0101110 不会看花眼？

哈夫曼码有个好脾气：任何一个字符的码，都不是另一个字符码的开头。看 0 就是 A；看到 10 就是 B——绝不会把 A 的「0」当成 B 的「0…」开头。这样一连串号码切分时永远只有一种切法，不会认错。

💡 口诀：短码不是长码的开头——这叫前缀码，切号码永不错。

🌀 格雷编码：相邻两个数，号码只差一位

普通二进制从 3 变到 4 是 011 → 100，三位全变了。可如果机器正在一个刻度一个刻度地转，三位一起变很容易读错。格雷码(Gray Code)专门解决这个问题：它给相邻数字发的号码每次只变一位。

🔢 3 位格雷码开头长这样

0 → 000　1 → 001　2 → 011　3 → 010　4 → 110…
000→001 只变最后一位；001→011 只变中间一位；011→010 又只变最后一位。挨着的两行永远只有 1 位不同。

💡 口诀：格雷码是「一步一变的楼梯」——相邻两码只差一位。

📟 行业实际：旋转编码器里的小圆盘

工厂机器、鼠标滚轮、相机旋钮里有一个带刻度的圆盘，圆盘转一格，机器要读出「现在到几了」。如果号码一次变好几位，圆盘正好卡在中间时就可能读错。用格雷码，转一格只变一位，怎么读都稳。

💡 口诀：转盘读数怕错位，格雷码一步只变一位最保险。

🆚 易混对比：哈夫曼编码 vs 格雷编码

这两个名字都带「编码」，但干的活儿完全不一样，别记混啦：

📊 一张表分清两兄弟

· 哈夫曼编码：给「字符」发码，目标是把文章变短（压缩）。特点是高频字符码短、用前缀码防看错。
· 格雷编码：给「数字」发码，目标是转盘读数更稳。特点是相邻两个数的码只差一位。

💡 口诀：哈夫曼管压缩要短码，格雷管读数要稳——差一位就行。

💼 身边哪里在用这两种码？

1️⃣ZIP 压缩包、图片、视频：压缩软件用哈夫曼编码把重复多的内容缩短，文件就变小了。
2️⃣机器人关节、打印机、鼠标：转动的位置传感器用格雷码，转一格只变一位，读数不会跳错。
3️⃣通信纠错：格雷码还用来减少信号在电线里传错的可能，让数据传得更稳。

🌟 一句话记住

哈夫曼让文件「变小」，格雷让机器「读得稳」——一个管省，一个管准。

💡 口诀：文件想变小找哈夫曼，转盘想读准找格雷。

🎯

闯关小锦囊 · 考点提醒

哈夫曼编码给字符发码：出现越多的字符码越短，整篇编码越省。
哈夫曼码是前缀码：任何字符的码不是另一个码的开头，一串码只有一种切法。
把出现次数当权值，哈夫曼树的带权路径长度最小——合并的权值一次次相加，就能算出整段文字最少要多少比特。
发码方法：从哈夫曼树根出发，往左记 0、往右记 1，走到字符的路径就是它的码。
格雷编码给数字发码：相邻两个数字的码只差一位。
格雷码常用于旋转编码器这类「一格一格读数」的机器，防止多位一起变读错。

🎮

学完了？来闯关！

下面 15 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。