哈夫曼树及其应用

admin

哈夫曼树
哈夫曼树又称最优二叉树，它是树的带权路径长度值最小的一棵二叉树，可用于构造最优编码，在信息传输，数据压缩等方面有着广泛的应用。

相关概念
路径：树中一个结点到另一个结点之间的分支序列。

路径长度：路径上分支的条数。

结点的权：给结点赋予的数值。

带权路径长度：结点的权值就是与该结点到数根间路径长度的乘积。

树的带权路径长度：树中所有叶子结点的带权路径长度之和，计为：WPL