1.哈夫曼树
二叉树上两个节点之间的路径长度：这条路径经过的边的长度。
树的路径长度：从根到每个节点的路径长度之和。
二叉树越平衡，树的路径长度越短，完全二叉树路径长度最短。
带权节点：
从根到一个带权节点的带权路径长度：从根到该节点的路径长度与节点权值的乘积。
树的带权路径长度：所有叶子节点的带权路径长度之和。
因为节点有权值，所以一棵平衡的二叉树并不一定有最小的带权路径长度。
给定n个权值，构造一棵有n个叶子节点的二叉树，每个叶子节点对应一个权值。
其中带权路径长度最小的二叉树称为哈夫曼树，或者最优二叉树。
构造方法：(贪心)把权值大的节点放在离根节点近的层次上，权值小的节点放在离根节点远的层次上。
哈夫曼树的构造过程
2.哈夫曼编码(“前缀”最优编码)
给定一串字符串，每种字符出现次数不同，将这串字符串编码成一个二进制数。
若把每个字符用相同长度二进制数编码，简单实用，但不节省空间；可以使用变长编码，频数高的字符用短码表示，频数低的用长码表示。
编码方案不能使某个编码是另一编码的前缀，两个编码又包含关系，就不能进行唯一的解码还原。
哈夫曼编码是前缀编码的一种最优算法。
构造：
二叉树左边为0，右边为1，编码放在叶子节点上，以保证“前缀不包含”。出现频次低的放在二叉树最深处，编码最长，频次高的最靠近根节点，编码最短。
构造过程同哈夫曼树构造。
