目录

简介哈夫曼树的构造哈夫曼编码         关于树与二叉树的其它概念和知识，可以看我的另一篇博客： 一篇文章读懂：树和二叉树

---

简介

        要想了解哈夫曼树（最优二叉树，或赫夫曼树），先要了解以下概念：

路径：从树中一个结点到另一个结点之间的分支构成两个结点之间 的路径；路径长度：路径上的分支数目。就是从一个结点到另一个结点有多少个路径；结点的路径长度：从根到该结点的路径长度；树的路径长度：从树根到每一个结点的路径长度之和；结点的权：在一些应用中，赋予树中结点的一个有某种意义实数；结点的带权路径长度：从根结点到该结点的路径长度与相应结点权值的乘积。树的带权路径长度：所有叶结点的带权路径长度之和；

        哈夫曼树是带权路径长度最短的树。

哈夫曼树的构造

一般步骤：

先对权值结点列表进行排序（从小到大）；取出权值最小的两个结点，小的为左孩子，大的为右孩子，和作为父节点，从结点列表中删除这两个结点，并将父结点作为新的结点加入结点列表中；重复以上步骤，直到集合中只剩一个元素。

举个例子：         对于权值结点列表{60, 45, 13, 69, 14, 5, 3}

        步骤一：排序{3, 5, 13, 14, 45, 60, 69}

        步骤二：

        排序：

        构造父结点：

        排序：

        构造父结点、排序：

        构造父结点：

哈夫曼编码

        向左分支为 0，向右分支为 1，从根到叶子的路径构成叶子的哈夫曼编码（前缀编码）。         如上述例子中的：{ A：60, B:45, C:13 D:69 E:14 F:5 G:3}，假设权值表示每种字符出现的频率         加上0、1编码后：

        则每个字符的二进制编码为：

A：10 B：01 C：0011 D：11 E：000 F：00101 G：00100

比如想传送BCD时，编码为：01001111         通过观察，哈夫曼树的它的字母都在叶子结点上，因此不会出现一个字母的编码为另一个字母编码左起子串的情况，可以避免编码冲突（编码冲突：一个字母的二进制代表数，为另一个字母的二进制代表数的子串）。         哈夫曼树的构造并不是唯一的，但带权路径长度都是最小的。         例如：{3， 5， 7， 8，14 }，可以有以下两种构造形式。