赫夫曼树

赫夫曼树是一类带权路径长度最短的树。

假设有 个权值 ，试构造一颗有 个叶子结点的二叉树，每个叶子结点带权为 ，则其中WPL最小的二叉树称为最优二叉树或霍夫曼树。

举个例子：假如现在有 A , B , C , D , E 这五个字符，它们分别出现的频率（即权值）为 5, 4, 3, 2, 1，下图为赫夫曼树的构建过程（每次取两个权值最小的节点生成一个树）：

笔记来源

可变长编码（赫夫曼编码，UTF-8编码