提出问题

计算机常用 位串（一串0和1组成的字符串） 来表示各种字符。如果想要用0和1表示26个英文字母，最少需要几位长度的位串呢？

作出假设

相信不少人想到的都是五位吧？因为 2⁵ = 32 > 26。这样我们每次只要取五位位串，便能表示清楚的出每个英文字母。
但还有没有更优的解法呢？如果表示英文字母的位串长度可以更少的话，在传输信息的过程中，就可以节省更多的存储空间，从而缩短传输数据的时间。

进一步假设

上面的方法是使用相同长度的位串表示英文字母，那么我们能不能用不同位数的位串表示不同的英文字母呢？

假设我们将 e编码成0，a编码成1，t编码成01，那么在用位串表示某些单词的时候，就会出现 “一串多义”的情况。比如 位串 0101 就对应着以下四种情况：

进一步思考

上面的例子似乎让我们想要用不同位数的位串表示不同英文字符的想法落空，但这种方式真的就不行吗？

我们把上面的 e，a，t 重新编码一下，这一次，我们把 e 编码成 0，a 编码成 10，t 编码成 11。我们接下来再来看看上面eaea，tt，eat，tea的位串。
我们随便抽取了几个例子，事实证明，按照这种方式编码，任何英文字母的组合，是不会出现重复的位串的。具有这种 没有位串对应着多种情况的序列 的性质的编码被称为前缀码。

如何才能保证 没有位串对应着多种情况的序列 的情况呢？我们只要令一个字母的位串永远不出现在另一个字母位串的开头部分即可。

进一步探索 （二叉树编码字符）

只是靠想，可能还是很难对英文字母进行编码，那我们应该怎么做呢？

通过我们常见的二叉树即可。
上图便是我们 e，a，t 这组前缀码的二叉树表示，其中字符是树种树叶的标记。

树的边也被标记，使得通向左子的边标记为0，通向右子的边标记为1。

我们可以用这种方式来编码一个字符的位串是在从根到以这个字符作为标记的树叶的唯一通路上标记的序列。

• 举个例子：
  下面的编码：
  • 0 → e
  • 10 → a
  • 110 → t
  • 1110 → n
  • 1111 → s

使用这种方式，我们就能找到一组前缀码了，就能对26个英文字母进行编码。

通常，为了节省空间，我们把常用的编码放在离树的根部最近的地方（位串长度最少），这样能节省更多的空间。比如 e 是 26 个英文字母所组成的单词种最常用的字母，我们就把 e 放在距离树根最近的地方，编码为 0。

拓展（二叉树解码位串）

二叉树解码位串，就是把上述编码的过程反过来即可。

举个例子：利用上述编码，解码 11111011100

所以最终解码的结果是 sane