Huffman tree(赫夫曼树、霍夫曼树、哈夫曼树、最优二叉树)

Huffman tree(赫夫曼树、霍夫曼树、哈夫曼树、最优二叉树)

flyfish 2015-8-1

Huffman tree因为翻译不同所以有其他的名字 赫夫曼树、霍夫曼树、哈夫曼树
定义引用自严蔚敏《数据结构》
路径
从树中一个结点到另一个结点之间的分支构成两个结点之间的路径.

路径长度
路径上的分支数目称作路径长度。

树的路径长度
树的路径长度就是从根节点到每一结点的路径长度之和。

结点的带权路径长度
结点的带权路径长度就是从该结点到根节点之间的路径长度与结点上权的乘积。

树的带权路径长度
树的带权路径长度就是树中所有叶子结点的带权路径长度之和，通常记做WPL。

Huffman tree
假设有n个权值{$w_1,w_2,…w_n$}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权$w_i$，则其中带权路径长度WPL最小的二叉树称作Huffman tree 。

假设有一个字符串每个字符出现的次数如下
A:5
B:15
C:40
D:30
E:10
将字符按照出现次数从小到大排序形成一个有序序列

自底向上建树过程
第一步

第二步

第三步

第四步

构造完成

概念补充