哈夫曼树（理论）

哈夫曼树是一种特殊的二叉树，这种树的所有的叶子结点都有权值，从而构造出带权路长度最短的二叉树，即哈夫曼树。

哈夫曼树的定义和相关概念

1. 路径
   • 一个结点与另一个结点之间的分支构成这两个结点之间的路径。（不是所有结点间都有路径，但从根节点到任一结点都存在一条路径）
2. 路径长度
   • 树中路径上的分支数目。
3. 树的路径长度
   • 根节点到每个结点的路径长度之和。
4. 叶子结点的权值
   • 人们根据需要为每个叶子结点赋予的一个数值。（哈夫曼树中，分支结点无需设权值）
5. 叶子结点的带权路径长度
   • 根到该叶子结点之间的路径长度与 X 该结点的权值。
6. 树的带权路径长度
   • 所有叶子结点的权值 X 该结点的路径长度之和。
7. 哈夫曼树
   • 又成为最优二叉树。是n个带权值的叶子结点所构成的所有二叉树中带权路径长度最小的二叉树。

构造方法

构造哈夫曼树的步骤：

1. 将给定的n个权值{w1, w2, ..., wn}作为n个根结点的权值，构造一个具有n棵二叉树的森林{T1, T2, ..., Tn}，其中每棵二叉树只有一个根结点。
2. 在森林中选取两棵树根结点权值最小的二叉树，作为左右子树，构造一棵新的二叉树。新二叉树的根节点的权值为原来两棵树根结点的权值之和。
3. 在森林中，将上面选择的这两棵根节点权值最小的树从森林中删除，并将最新构造的二叉树加入到森林中。
4. 重复上面2、3，直到森林中只有一棵二叉树树为止。这课二叉树就是哈夫曼树。

哈夫曼树的构造算法：
在构造哈夫曼树时，可以设置一个结构数组HT，用来保存各结点的信息。
由二叉树的性质可知：具有n个叶子结点的哈夫曼树共有2n-1个结点，所以2n-1即数组HT所需的存储空间。
其结构如下：

{
    weight;
    lchild;
    rchild;
    parent;
    ...
};
1
2
3
4
5
6
7

其中，

• weight保存结点权值；
• lchild、rchild保存结点的左右孩子结点在数组HT中的序号；
• parent判定一个结点是否已经加入到建立的树中；
• 初始时，parent值为-1，当结点加入到树中时，该结点的parent值为其父结点在数组HT中的序号。

生成哈夫曼编码的方法

要设计长度不同的编码，首先要做到不同字符的编码不会混淆，即任一个编码都不是另一个编码的开头一部分，满足这个条件的编码叫做前缀编码。

1. 构造哈夫曼树。设需要编码的字符集合为{d1, d2, … , dn}，权值为{w1, w2,…, wn}，以d1, d2, … ,dn为叶子结点，w1, w2, …, wn为权值，构造哈夫曼树。
2. 在哈夫曼树上求叶子结点的编码。规定哈夫曼树中左分支代表0，右分支代表1，则从根节点到每个叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码。