赫夫曼树

赫夫曼树

赫夫曼树 : 又称之为哈夫曼树

赫夫曼树的基本介绍:

1. 给定n个权值作为n个叶子结点, 构造一颗二叉树, 若该树的带权路径长度(WPL)达到最小, 称这样的二叉树为最优二叉树, 也称为: 哈夫曼树(Huffman Tree)

   • 有的地方也翻译为: 霍夫曼树
   • 带权路径长度: WPL(Weighted Path Length)

2. 赫夫曼树是带权路径最短的树

   • 赫夫曼树的特点就是: 权值越小的节点离根节点最远

路径:

在一棵树中,从一个节点往下可以达到的孩子或者孙子节点之间的通路称之为路径

路径长度:

一条通路中分支的数目称之为路径长度, 若规定根节点层数为L , 则从根节点到L层节点的路径长度为L-1

节点的权:

若给树节点赋一个有某种含义的数值, 则这个数值称为该结点的权

结点的带权路径长度:

从根节点到该节点之间的路径长度与该节点的权值的乘积称之为该结点的带权路径长度

树的带权路径长度:

数的带权路径长度规定为所有的叶子结点的带权路径之和,记为WPL

• 权值越大的结点,离根结点越近的二叉树才是最优二叉树
• 注意: 这里不是所有节点的带权路径之和,而是所有的叶子结点的带权路径之和

WPL最小的就是赫夫曼树

图解: