最优二叉树，也称哈夫曼(Haffman)树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。

那么什么是二叉树的带权路径长度呢?

在前面我们介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根结点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，则可将这一概念加以推广。设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度，记为:

WPL= Wk·Lk

其中Wk为第k个叶结点的权值，Lk 为第k个叶结点的路径长度。如图7.2所示的二叉树，它的带权路径长度值WPL=2×2+4×2+5×2+3×2=28。

在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个叶结点，设其权值分别为1，3，5，7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。图7.3给出了其中5个不同形状的二叉树。

这五棵树的带权路径长度分别为:

(a)WPL=1×2+3×2+5×2+7×2=32

(b)WPL=1×3+3×3+5×2+7×1=29

(c)WPL=1×2+3×3+5×3+7×1=33

(d)WPL=7×3+5×3+3×2+1×1=43

(e)WPL=7×1+5×2+3×3+1×3=29

最优二叉树算法

最优二叉树算法

由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树(即哈夫曼树)呢?根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。

哈夫曼(Haffman)依据这一特点于1952年提出了一种方法，这种方法的基本思想是:

(1)由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F={T1，T2，…，Tn};

(2)在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和;

(3)在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中;

(4)重复(2)(3)两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。

在实际应用中，常常要考虑一个问题:如何设计一棵二叉树，使得执行路径最短，即算法的效率最高。

例1.快递包裹的邮资问题

假设邮政局的包裹自动测试系统能够测出包裹的重量，如何设计一棵二叉树将包裹根据重量及运距进行分类从而确定邮资。

国内快递包裹资费 单位:元

(2004年1月1日起执行)

表1 国家邮政局制定的快递包裹参考标准

根据表1可以制定出许多种二叉树，但不同的二叉树判定的次数可能不一样，执行的效率也不同。

铁球分类

现有一批球磨机上的铁球，需要将它分成四类:直径不大于20的属于第一类;直径大于20而不大于50的属于第二类;直径大于50而不大于100的属于第三类;其余的属于第四类;假定这批球中属于第一、二、三、四类铁球的个数之比例是1:2:3:4。

我们可以把这个判断过程表示为 图1中的两种方法:

最优二叉树算法

两种判断二叉树示意图

那么究竟将这个判断过程表示成哪一个判断框，才能使其执行时间最短呢?让我们对上述判断框做一具体的分析。

假设有1000个铁球，则各类铁球的个数分别为:100、200、300、400;

对于图7.1中的上图和下图比较的次数分别如表所示:

左图 和下图

表2 两种判断二叉树比较次数

过上述分析可知，图1中右图所示的判断框的比较次数远远小于左图所示的判断框的比较次数。为了找出比较次数最少的判断框，将涉及到树的路径长度问题。

在本章的引入部分，两个例子都是判定问题，这两个判定问题都可以通过构造哈夫曼树来优化判定，以达到总的判定次数最少。

再如，要编制一个将百分制转换为五级分制的程序。显然，此程序很简单，只要利用条件语句便可完成。

程序段

if a<60 then b:='bad'

else if a<70 then b:='pass'

else if a<80 then b:='general'

else if a<90 then b:='good'

else b:='excellent';

如果上述程序需反复使用，而且每次的输入量很大，则应考虑上述程序的质量问题，即其操作所需要的时间。因为在实际中，学生的成绩在五个等级上的分布是不均匀的，假设其分布规律如表4所示:

表4 分数段的分布频率

则80%以上的数据需进行三次或三次以上的比较才能得出结果。假定以5，15，40，30和10为权构造一棵有五个叶子结点的哈夫曼树，它可使大部分的数据经过较少的比较次数得出结果。但由于每个判定框都有两次比较，将这两次比较分开，得到新的判定树，按此判定树可写出相应的程序。请您自己画出此判定树。

假设有10000个输入数据，若上程序段的判定过程进行操作，则总共需进行31500次比较;而若新判定树的判定过程进行操作，则总共仅需进行22000次比较。

如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。

可以根据公式进行推导，假设n0是度为0的结点总数(即叶子结点数)，n1是度为1的结点总数，n2是度为2的结点总数，则 ①n= n0+n1+n2 (其中n为完全二叉树的结点总数);又因为一个度为2的结点会有2个子结点，一个度为1的结点会有1个子结点，除根结点外其他结点都有父结点，所以②n= 1+n1+2*n2 ;由①、②两式把n2消去得:n= 2*n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。

简便来算，就是 n0=n/2，其中n为奇数时(n1=0)向上取整;n为偶数时(n1=1)。可根据完全二叉树的结点总数计算出叶子结点数。

由于网络所有可能的划分数量是巨大的，假设网络的结点数和边数分别为n和m，则所有可能的社区划分数是一个以n为指数的数。因此，在所有可能的划分中找出最优划分是一个NP-hard问题。针对这一问题，目前一些相应算法已被提出，其可以在合理的时间内找出模块度最大化的近似最优划分。

模块度最大化问题是一个经典的最优化问题，Mark NewMan 基于贪心思想提出了模块度最大化的贪心算法FN 。贪心思想的目标是找出目标函数的整体最优值或者近似最优值，它将整体最优化问题分解为局部最优化问题，找出每个局部最优值，最终将局部最优值整合成整体的近似最优值。FN算法将模块度最优化问题分解为模块度局部最优化问题，初始时，算法将网络中的每个结点都看成独立的小社区。然后，考虑所有相连社区两两合并的情况，计算每种合并带来的模块度的增量。基于贪心原则，选取使模块度增长最大或者减小最少的两个社区，将它们合并成一个社区。如此循环迭代，直到所有结点合并成一个社区。随着迭代的进行，网络总的模块度是不断变化的，在模块度的整个变化过程中，其最大值对应网络的社区划分即为近似的最优社区划分。

贪心算法FN具体步骤:

该算法中，需要注意的是，每次加入的边只是影响网络的社区划分，而每次计算网络划分的模块度时，都是在网络完整的拓扑结构上进行，即网络所有的边都存在的拓扑结构上。

为了降低算法的时间复杂度，Vincent Blondel等人提出了另一种层次贪心算法 。该算法包括两个阶段，第一阶段合并社区，算法将每个结点当作一个社区，基于模块度增量最大化标准决定你哪些邻居社区应该被合并。经过一轮扫描后开始第二阶段，算法将第一阶段发现的所有社区重新看成结点，构建新的网络，在新网络上重复进行第一阶段，这两个阶段重复运行，直到网络社区划分的模块度不再增长，得到网络的社区近似最优划分。

这个简单算法具有一下几个优点:首先，算法的步骤比较直观并且易于实现;其次，算法不需要提前设定网络的社区数，并且该算法可以呈现网络的完整的分层社区结构，能够发现在线社交网络的分层的虚拟社区结构，获得不同分辨率的虚拟社区;再次，计算机模拟实验显示，在稀疏网络上，算法是时间复杂度是线性的，在合理的时间内可以处理结点数超过10^9的网络，因此十分适合在线社交网络这样超大规模的负责网络中虚拟社区的发现。

是程序算法中的一种算法模式。

在二叉树中出现空的子树（包括树叶）上增加空的树叶，使其成为满二叉树的二叉树称之为扩充二叉树。