|
|
|
最优二叉树又称为哈夫曼树，是一类带权路径长度最短的树。
|
|
|
|
从树中一个结点到另一个结点之间的通路称为结点间的路径，该通路上分支数目称为路径长度。树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积。
|
|
|
|
树的带权路径长度为树中所有叶子结点的带权路径长度之和，记为：
|
|
|
|
|
|
其中，n为带权叶子结点数目，wk为叶子结点的权值，lk为叶子结点到根结点的路径长度。
|
|
|
|
最优二叉树是指权值为w1，w2，…，wn的n个叶子结点的二叉树中带权路径长度最小的二叉树。例如，在下图中所示的具有4个叶子结点的二叉树中，以下图（b）所示二叉树的带权路径长度最小。
|
|
|
|
|
|
|
|
|
|
（1）根据给定的n个权值｛w1，w2，…，wn｝构成n棵二叉树的集合F=｛T1，T2，…，Tn｝，其中每棵树Ti中只有一个带权为wi的根结点，其左右子树均空。
|
|
|
|
（2）在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。
|
|
|
|
（3）从F中删除这两棵树，同时将新得到的二叉树加入到F中。
|
|
|
|
重复（2）、（3）步，直到F中只含一棵树时为止，这棵树便是最优二叉树（哈夫曼树）。
|
|
|
|
最优二叉树的一个应用是对字符集中的字符进行编码和译码。
|
|
|
|
对给定的字符集D=｛d1，d2，…，dn｝及权值集合W=｛w1，w2，…，wn｝，构造其哈夫曼编码的方法为：以d1，d2，…，dn作为叶子结点，w1，w2，…，wn作为对应叶子结点的权值，构造出一棵最优二叉树，然后将树中每个结点的左分支标上0，右分支标上1，则每个叶子结点代表的字符的编码就是从根到叶子的路径上的0、1字符组成的串。
|
|
|
|
例如，设有字符集｛a，b，c，d，e｝及对应的权值集合｛0.30，0.25，0.15，0.22，0.08｝，按照构造最优二叉树的哈夫曼方法：先取字符c和e所对应的结点构造一棵二叉树（根结点的权值为c和e的权值之和），然后与d对应的结点分别作为左、右子树构造二叉树，之后选a和b所对应的结点作为左、右子树构造二叉树，最后得到的最优二叉树（哈夫曼树）如下图所示。其中，字符a的编码为00，字符b、c、d、e的编码分别为01、100、11、101。译码时就从树根开始，若编码序列中当前编码为0，则进入当前结点的左子树，为1则进入右子树，到达叶子时一个字符就翻译出来了，然后再从树根开始重复上述过程，直到编码序列结束。例如，若编码序列101110000100对应的字符编码采用下图所示的树进行构造，则可翻译出字符序列"edaac"。
|
|
|
|
|
|
|
