学科分类
目录
数据结构

什么是霍夫曼树

在了解霍夫曼树之前,首先来学习几个术语:

1、路径: 6.1.1节已经学习过路径这个概念,它是指从某一结点到另一个结点的线路。

2、树的路径长度:树的路径长度是从树根到树中每一个结点的路径长度之和。如图1所示,其路径长度为1+1+2+2+2+2+3+3=16。

图1 二叉树

结点数目相同的所有二叉树中,完全二叉树的路径长度最短。

3、树的带权路径长度(Weighted Path Length of Tree,简记为WPL):

结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。例如用树结点存储一些字符时,可以用字符的ASCII码值作为结点权值;用树结点存储学生成绩划分时,那么学习成绩就可以是权值。

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

树的带权路径长度(WPL):树中所有叶结点的带权路径长度之和,通常记为:

其中,n表示叶子结点数目;wi和li分别表示结点ki的数值和根到结点ki之间的路径长度。树的代权路径长度亦称为树的代价。

在由权为w1,w2,…,wn的n个叶子结点所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树。因为它是数学家霍夫曼(Huffuman)所提出,所以也叫作霍夫曼树。

假设一棵有4个叶子结点a,b,c,d的二叉树,带的权分别为7,5,2,4,我们构造出三棵结构不同但都有4个叶子结点的二叉树,如图2所示。

图2 有4个结点的三种二叉树形式

它们的带权路径长度分别为:

①WPL=7×2+2×2+5×2+4×2 = 36;

②WPL=7×1+5×2+2×3+4×3 = 35;

③WPL=7×2+2×3+5×3+4×1 = 39。

其中②中的二叉树是霍夫曼树,它的WPL最小。读者也可以再构建有4个结点的其他二叉树来计算树的带权路径长度,但它们都会比②中二叉树的值大。

当叶子结点的权值均相同时,权越大的叶子离根越近,权越小的叶子离根越远,树的代价就越小。注意:霍夫曼树的形态并不唯一。

点击此处
隐藏目录