求Huffman树的带权路径长度-创新互联

Huffman树的建立过程：

首先得到整个叶子结点的集合：

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：申请域名、网页空间、营销软件、网站建设、隆阳网站维护、网站推广。

求Huffman树的带权路径长度算法：

书上讲常见的求Huffman树的带权路径长度算法为：从叶子结点权值乘路径长度：

WPL=7*2+5*2+5*2+3*3+2*3=49

另外一种求WPL的算法为：非叶子几点权值之和：

WPL=22+12+10+5=49

这种方法并不是毫无道理，应为同一个结点下的两个叶子结点的路径长度是一样的，叶子结点的路径长度完全可以反映到其双亲结点上去。

这种算法较为简单，直接可以忽略建树的步骤，直接求出WPL（当然要明白如何求WPL）

算法的主要思想：

1.首先将得到的元素集合进行排序；（降序。升序也行，请自己尝试）

2.数组末尾两个元素求和（俩结点的双亲结点权值），将其结果放在数组倒数第二个位置上并且数组长度减1

3.累加每次求和结果。（即就是非叶子结点的权值）

注意：当集合元素过小时不适用本算法，需要特殊处理，不然会发生数组越界。

C语言实现：

#include#include// 算法思想：
// 本题主要为求哈夫曼树的带权路径长度，故未将重点放在建树上
// Huffman树的带权路径长其实就是其非叶子结点的权值和

//排序算法
void sort(int *data,int n){
    int i,j;
    for(i =0;i

运行测试：

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


当前文章：求Huffman树的带权路径长度-创新互联
浏览地址：http://cdkjz.cn/article/csecoi.html