Tag Archives: 赫夫曼树

数据结构重读 – 赫夫曼树(最优二叉树)

路径长度:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称作路径长度。

树的路径长度:从树根到每一个结点的路径长度之和。

结点的带全路径长度:从该结点到树根之间的路径长度与结点上权的乘积。

树的带全路径长度:树中所有叶子结点的带全路径长度之和,WPL = Σ (wi x li),其中wi是叶子结点的权重,li是从根到该叶子结点的路径长度,注意,带全路径长度只有叶子结点有权重!其他结点只计算长度无权重!

来看书上三个树的WPL:

[......]

继续阅读