哈夫曼树也是一种特殊的二叉树,这种树的所有叶子结点都带有权值,从中构造出带权路径长度最短的二叉树。

路径长度(Path Length,PL)

图片.png
图片.png
图片.png

带权路径长度(Weighted Path Length,WPL)

图片.png
图片.png

霍夫曼树

1. 特点

  • 带权路径长度达到最小的扩充二叉树即为霍夫曼树。
  • 在霍夫曼树中,权值大的结点离根最近。

    2. 霍夫曼算法

    图片.png
    图片.png

    3. 霍夫曼树的构造过程