哈弗曼树/霍夫曼树

一些概念

路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；
路径长度：路径上的分支数目称为路径长度；
树的路径长度：从根到每个结点的路径长度之和。
结点的权：根据应用的需要可以给树的结点赋权值；
结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；
树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=∑wi×li
哈夫曼树：假设有n个权值(w1, w2, … , wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。
前缀码的定义：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。霍夫曼编码就是前缀码，可用于快速判断霍夫曼编码是否正确。霍夫曼树是满二叉树，若有n个节点，则共有(n+1)/2个码子

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树(Huffman Tree)。霍夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。哈夫曼树的结点个数必为奇数。

哈夫曼树不一定是完全二叉树，但一定是最优二叉树。

若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为[(n-1)/(m-1)]。边的数目等于度。