数据结构—最优二叉树（赫夫曼树）详解

当我们知道了数、森林、二叉树之后。我们就很好理解最优二叉树，下面从这两个方面展开讨论来认识最优二叉树。

一.什么样的数是最优二叉树？

权：指两个节点的长度值

树的带全路径=所有叶子节点的带权路径之和，

树的路径长度：从树根到每个叶子节点的路径长度之和

eg.

下面我们根据树的带权路径计算公式来判定一下哪棵树是最优二叉树，

WPL=7*2+5*2+2*2+2*4=36——a

WPL=7*3+5*3+2*1+4*2=46——b

WPL=7*1+5*2+2*3+4*3=35——c

由此我们可以看出，（c）即为最优二叉树

 

二.怎样得到一棵最优二叉树？

赫夫曼给出了一个带有一般规律的算法，俗称赫夫曼算法

（1）根据给定的n个权值（w1,,w2,w3......wn）构成n棵二叉树集合F={T1,T2,T3......Tn}其中每棵二叉树Ti中只有一个带权的Wi的根节点其左右子树均空。

（2）在F中选取两课根节点的权值最小的树作为左右子树构成一棵新的二叉树，且置新的二叉树根结点的权值为左右子树上根结点的权值之和。

（3）在F中删除这两棵树，同时将新得到的二叉树加入F中。

（4）重复进行（2）（3），直到F只含一棵树为止，这棵树便是赫夫曼树。

构造过程如下：

赫夫曼树共有2n-1个结点（n表示叶子结点树）