哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
例子。
（3）不断重复（2）的过程直到队列中的节点个数为1之时，我们便得到了一颗哈夫曼树。
6、继续用倒V型的树杈，向上延伸，算出最后一个结果，就证明哈夫曼树构建成功。
哈夫曼树的构造规则是若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
在一棵树中，从一个结点往下可以达到的孩子或孙子。
夫曼树是带权路径长度最小的二叉树，用途是平均查找信息的代价最小。
普通二叉树的用途也普通，比较通用，就是信息存储和查找。
普通二叉树可能有的只有一个子节点，而哈夫曼树一定有两个。