2．设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL.4．设一组初始记录关键字集合为(25,10,8,27,32,68),散列表的长度为8,散列函数H(k)=k mod 7,要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表.
问题描述：
2．设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL.
4．设一组初始记录关键字集合为(25,10,8,27,32,68),散列表的长度为8,散列函数H(k)=k mod 7,要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表.
答
设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树
夫曼树的构造：
（1）根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn},其中Ti中只有一个权值为wi的根结点,左右子树为空；
（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树,且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和.
（3）将新的二叉树加入到F中,删除原两棵根结点权值最小的树；
（4）重复（2）和（3）直到F中只含一棵树为止,这棵树就是哈夫曼树.
哈夫曼.bmp (134.99 KB)
2008-8-5 17:55
以上图片是过程
最后的树是这样：
35
20 15
9 11 7 8
3 5
wpl=3*3 5*3 7*2 9*2 11*2=78
本文来自:冠威计算机网(