1. 树和二叉树的应用之赫夫曼树和赫夫曼编码

1.概念
赫夫曼树又叫做最优二叉树，特点为带权路径最短

• 路径 ： 指从树中一个结点到另一个结点的分支所构成的路径
• 路径长度 ： 指路径上的分支数目（边数）
• 树的路径长度 ： 指从根到每个结点的路径长度之和
• 带权路径长度 ： 结点具有权值，从该结点到根结点的路径长度（边数）乘以该结点的权值，就是该结点的带权路径长度

带权路径长度 = 结点的权 * 结点至根结点的路径长度

• 树的带权路径长度（WPL） ： 树中所有叶子结点的带权路径长度之和

树的带权路径长度 = ∑( 叶子结点的权 * 叶子结点至根结点的路径长度)

2.赫夫曼树的构造

• 每次取权值最小的结点构造

[注] 赫夫曼树的构造结果不唯一
为了使得到的哈夫曼树的结构尽量唯一，通常规定生成的赫夫曼树中每个结点的左子树根结点的权小于等于右子树根结点的权

示例：构造的过程
对5个结点进行赫夫曼树构造

赫夫曼树构造

3.赫夫曼树的特点

1. 权值越大的结点，距离根结点越近
2. 树中没有度为1的结点；这类树又叫做正则二叉树

4.赫夫曼编码
    在编码传递的过程中，总希望编码的长度短一点，可行的办法就是为每一个字符设置长度不同的编码，出现频率高的字符，设置的编码长度短一点！
    为避免二义性，引入前缀编码的概念

前缀编码　：　任何一个字符的编码都不是另一个字符的前缀

    为了同时满足长度最短和前缀编码两个要求，引入赫夫曼编码

赫夫曼编码 ：　长度最短的前缀编码；
即给定要传递的字符的权值，根据权值求出赫夫曼编码。