哈夫曼树

哈夫曼树也称为最优树，它是一类带全路径长度最短的树，最先需要掌握的是它的几个简单的基本概念。

哈夫曼树

别称

最优树

是一类带权路径长度最短的树

路径和路径长度

路径

指的是

从树中一个节点

到另一个节点

所构成的

路线

路径长度

路径上的分枝数目

分枝数目

树的路径长度

指的是从树根到每一节点的

路径长度之和

树的带权路径长度

若将书中节点赋给一个有着某种含义的数值

数值

称为该节点的权

为所有叶子节点的带权路径长度之和

记为

n为叶子节点数目

为第k个叶子节点的权值

为第k个叶子节点的路径长度

特点

如果有n个带权值的叶子节点

可使用这些叶子节点生成很多二叉树

这些二叉树中带权路径长度WPL最小的二叉树称为

哈夫曼树

哈夫曼树并不唯一

或者也可以称为最优二叉树

最优二叉树