精华内容
下载资源
问答
  • 常用操作: 哈夫曼带权路径长度

    常用操作:在这里插入图片描述
    在这里插入图片描述
    哈夫曼树带权路径长度:
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 在一批数中, 选择两个最小的数字,用一个类似于树杈的“树枝”连接上两个最小的数。在顶点处计算出这两个数字的和 并写在上面。然后再比较剩下的数字和这个和的大小,再取出两个最小的数字进行排列
  • 已知输入一串正整数,正整数之间用空格键分开,请建立一个哈夫曼树,以输入的数字为叶节点,求这棵哈夫曼树的带权路径长度。 【输入形式】 首先输入正整数的个数,然后接下来为接下来的正整数,正整数个数不超过10个...

    【问题描述】
    已知输入一串正整数,正整数之间用空格键分开,请建立一个哈夫曼树,以输入的数字为叶节点,求这棵哈夫曼树的带权路径长度。

    【输入形式】
    首先输入正整数的个数,然后接下来为接下来的正整数,正整数个数不超过10个

    【输出形式】
    输出相应的权值

    【样例输入】
    5 4 5 6 7 8

    【样例输出】
    69

    【样例说明】

    【评分标准】

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct
    {
    	unsigned int weight;
    	unsigned int parent,lchild,rchild;
    }HTNode,*HuffmanTree;
    
    void Select(HuffmanTree HT,int n,int &s1,int &s2)
    {
    	
    	for(int i=1;i<=n;i++)
    	{
    		if(HT[i].parent==0)
    		{	s1=i;
    			break;
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		if(HT[i].parent==0&&HT[i].weight<=HT[s1].weight)
    			s1=i; 
    	}
    	
    	for(int i=1;i<=n;i++)
    	{
    		if(HT[i].parent==0&&i!=s1)
    		{	s2=i;
    			break;
    		}
    	}
    	
    			
    	for(int i=1;i<=n;i++)
    	{
    		if(HT[i].parent==0&&HT[i].weight<=HT[s2].weight&&i!=s1)
    			s2=i;
    	}
    	
    }
    void HuffmanCoding(HuffmanTree &HT,int *w,int n)
    {
    	if(n<=1) return;
    	int m=2*n-1;
    	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    	HuffmanTree p=HT+1;
    	int i,s1,s2;
    	for(i=1;i<=n;i++,p++ ,w++)  //前n个节点放n个叶子
    	{
    		p->weight=*w;
    		p->parent=0;
    		p->rchild=0;
    		p->lchild=0;
    	}
    	for(;i<=m;i++,p++)  //后面n-1放有孩子的节点
    	{
    		p->weight=0;
    		p->parent=0;
    		p->rchild=0;
    		p->lchild=0;
    	}
    	for(i=n+1;i<=m;i++) //建立哈夫曼树
    	{
    		Select(HT,i-1,s1,s2);
    		//printf("%d %d\n",s1,s2);
    		HT[s1].parent=i;
    		HT[s2].parent=i;
    		HT[i].lchild=s1;
    		HT[i].rchild=s2;
    		HT[i].weight=HT[s1].weight+HT[s2].weight;
    	}
    }
    
    int WeightLength(HuffmanTree HT,int n)  //n个叶子
    {
    	int c,s=0;//c是路径长度,s是带权路径长度
    	for(int i=1;i<=n;i++)
    	{
    		c=0;
    		int k=i;
    		while(HT[k].parent!=0)
    		{
    			k=HT[k].parent;
    			c++;	
    		}
    		s=s+c*HT[i].weight;
    	}
    	return s;
    }
    
    int main()
    {
    	int n;
    	HuffmanTree HT;
    	scanf("%d",&n);
    	int w[100];
    	for(int i=0;i<n;i++)
    		scanf("%d",&w[i]);
    	HuffmanCoding(HT,w,n);
    	printf("%d",WeightLength(HT,n));
    	return 0;
    }
    
    展开全文
  • 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出哈夫曼树的带权路径长度(WPL)。 输入格式: 第一行输入一个数n,第二行输入n个叶结点(叶结点权值不超过1000,2<=n&...

    题目描述:
    哈夫曼树,第一行输入一个数n,表示叶结点的个数。
    需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出哈夫曼树的带权路径长度(WPL)。

    输入格式:
    第一行输入一个数n,第二行输入n个叶结点(叶结点权值不超过1000,2<=n<=1000)。

    输出格式:
    在一行中输出WPL值。

    输入样例:
    5
    1 2 2 5 9

    输出样例:
    37

    参考代码:

    #include <stdio.h>
    
    #define INF 65535
    
    struct huffman{
    	int w;
    	int parent,lchild,rchild;
    }HT[1001];
    
    int n;
    
    void createHT()
    {
    	
    	int i,j;
    	//初始化 
    	for(i=0;i<2*n-1;i++)
    	 HT[i].parent=HT[i].lchild=HT[i].rchild=-1;
    	 
    	for(i=0;i<n;i++)
    	  scanf("%d",&HT[i].w);
    	
    	/*选用两小添新树
    	  删除两小添新人。*/ 
    	int a,b; 
    	int a1,b1; 
        for(i=0;i<n-1;i++)
        {
        	a1=b1=INF;
        	for(j=0;j<n+i;j++)
        	{
        		 if(HT[j].parent==-1&&HT[j].w<a1)
        		{
        			b=a;
        			a=j;
        			b1=a1;
        			a1=HT[j].w;
    			}
    			else if(HT[j].parent==-1&&HT[j].w<b1)
    			{
    				b=j;
    				b1=HT[j].w;
    			}	
    		}
    		
    		HT[n+i].w=HT[a].w+HT[b].w;
    		HT[n+i].lchild=a;
    		HT[n+i].rchild=b;
    		HT[a].parent=HT[b].parent=n+i; 
    	}
    }
    
    int main()
    {
    	while(scanf("%d",&n)!=EOF)
    	{
    		int i,sum=0;
    	    
    		createHT();
    		for(i=n;i<2*n-1;i++)
    		 sum+=HT[i].w;
    		 
    		printf("%d\n",sum);
    	}
    	return 0;
    } 
    

    参考资料:
    传送门

    展开全文
  • 哈夫曼带权路径长度

    万次阅读 多人点赞 2018-08-13 16:24:51
    可见,图b的带权路径长度较小,我们可以证明图b就是哈夫曼树(也称为最优二叉树)。   二. 怎么生成和计算? 1. 总结 ①先对权值从小到大排序。 ②选两个最小的加起来成为一个新结点,而这两个最小的值是新结点...

    一. 长什么样?

    左边是普通树,右边是哈夫曼树

    图a: WPL=5*2+7*2+2*2+13*2=54

    图b: WPL=5*3+2*3+7*2+13*1=48

    可见,图b的带权路径长度较小,我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

     

    二. 怎么生成和计算?

    1. 总结

    ①先对权值从小到大排序。

    ②选两个最小的加起来成为一个新结点,而这两个最小的值是新结点的左右子结点。

    ③两个老的结点去掉,新的结点放入再次排序然后重复过程②。

    ④直到完全生成一棵树。

    ⑤计算的时候,只计算那些初始权值里面有的值,把它乘以深度(和传统说的深度不一样,是传统说的深度减一)加起来就是路径长度。

    2. 例子

    例:对于给定的一组权值w={1,4,9,16,25,36,49,64,81,100},构造具有最小带权外部路径长度的扩充二叉树,并求出他的的带权外部路径长度。

    解答过程(红色表示原来的权值结点,蓝色是加出来的结点):

    带权外部路径长度计算:

    WPL=2*100 + 3*64 + 2*81 + 4*25 + 3*49 + 3*36 + 5*16 + 6*9 + 7*1 + 7*4 =1078

    展开全文
  • 哈夫曼树与带权路径长度

    万次阅读 多人点赞 2019-03-03 20:50:18
    权值分别为从19,21,2,3,6,7,10,32的结点,构造一棵哈夫曼树,该树的带权路径长度是? 构建哈夫曼树: 1.从19,21,2,3,6,7,10,32之中选取连个最小的2,3。 2.从19,21,5,6,7,10,32之中选取...
  • void WPL() 计算带权路径长度 所选实例: 所选实例 创建哈夫曼树 步骤: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1) 将w1、w2、...
  • 哈夫曼带权路径长度WPL

    万次阅读 多人点赞 2016-03-20 00:25:43
    (从第0层开始)WPL = 2 * 3(长度为3的编码形式)+3*3 + (4+5+6)*2 = 45; 这是定义的计算WPL的方式,然后我们看一下另一个奇妙的结果20 + 9 + 11 + 5 = 45; 证明如下:(证明并不充分 详细点的证明和...
  • 题目所描述的有点问题,其实是叶节点的路径与权值乘积之和,即带权路径长度! 用到了c++中小顶堆的创建方法,优先队列。 定义:priority_queue<Type, Container, Functional> Type 就是数据类型,Container ...
  • 计算方法: ①先对集合中的结点按照权值从小到大排。 ②选两个权值最小的结点,将它们...⑤计算的时候,只计算那些初始权值里面有的值,把它们的【权值】*【权值到根节点的距离】,再全部相加得到带权路径长度。 ...
  • 哈夫曼带权路径长度

    万次阅读 2015-01-16 19:05:31
     已知输入两行正整数,第二行正整数之间用空格键分开,请建立一个哈夫曼树,以输入的数字为叶节点,求这棵哈夫曼树的带权路径长度。 【输入形式】  首先第一行为输入正整数的个数,然后接下来的一行正整数,代表叶...
  • 哈夫曼树的带权路径长度和:所有构造得到的中间结点(非叶子结点)的权值和 构造中,每次寻找权值最小的两个结点,使用堆优化指logn #include<iostream> #include<cstdio> #include<queue&...
  • 给出叶子节点,输出带权路径长度 #include<queue> #include<stdio.h> using namespace std; priority_queue<int,vector<int>,greater<int> >q; int main() { int n,x,i; scanf("%d...
  • 最近刷题刷到了这一题,此...需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入描述: 输入有多组数据。 每组第一行输入一个数n,接着...
  • 已知输入一串正整数,正整数之间用空格键分开,请建立一个哈夫曼树,以输入的数字为叶节点,求这棵哈夫曼树的带权路径长度。 【输入形式】 首先输入正整数的个数,然后接下来为接下来的正整数,正整数个数不超过10个...
  • 笔试题:哈夫曼编码{4,9,2,7,5,12}的带权路径长度 解决思路: 首先构造哈夫曼树 在使用WPL=(W1*L1+W2*L2+W3*L3+…+Wn*Ln)计算带权路径长度 实现: 构造哈夫曼树: 每次取出最小的两个数构造第一层,在给出的...
  • 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过...
  • 思想: 先构建一个线性表,将树的结点存入,然后对树的结点进行升序排序,这样就保证了线性表的前两...而寻找带权路径长度可以使用递归的方法。 代码: public class Main { public static void main(String[] args) {
  • 哈夫曼树的带权路径长度=所有叶子节点的带权路径长度和 应该也知道还有另一种算法 哈夫曼树的带权路径长度=所有非叶子结点的权值和 ![图片说明](https://img-ask.csdn.net/upload/201604/04/1459752161_872418.jpg...
  • 哈夫曼树是WPL(带权路径长度)最小的二叉树。使用这种思想,提出哈夫曼编码,节省空间。
  • 哈夫曼树 题目描述 哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和的最小值。 输入描述...
  • 哈夫曼树:一类带权路径最短的树。用于通讯及数据传送中构造传输效率最高的二进制编码(哈夫曼编码),用于编程中构造平均执行时间最短的最佳判断过程。节点之间的路径长度:从一个节点到另一个节点之间的分支数目。...
  • 哈夫曼带权路径

    2021-09-18 16:01:25
    一般的,我们是可以用常规的构造哈夫曼树求带权路径长度。 计算结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。 带权路径长度WPL(Weighted Path Length)最小的二叉树,也称为最优二又树。 在...
  • 注意:哈夫曼树并不唯一,但带权路径长度一定是相同的。 二叉树:每个结点最多含有两个子树的树称为二叉树。 定理:对于具有n个叶子结点的哈夫曼树,共有2n-1个结点。 哈夫曼树介绍 1哈夫曼树的定义 哈夫曼...
  • 树的所有叶子结点的带权路径长度之和,称为树的带权路径长度,英文缩写为 `WPL`,从百度百科中得到的信息为 “树的带权路径长度(weighted path length of tree)是2018年公布的计算机科学技术名词”,这就有点奇怪...
  • 哈夫曼树与带权路径长度计算

    万次阅读 2018-09-18 10:35:48
    假设我们一个权重为1,7,3,13,12,15,24怎么样画出哈夫曼树和计算带权路径长度。 首先,选出最小的两个权重值,这里是1,3(矩形表示叶子节点,圆表示根节点也是两个叶子节点的和)如图: 然后,选出第三小的7,算...
  • 树的带权路径长度WPL 哈夫曼树构造 哈夫曼树性质 哈夫曼编码 试题
  •  已知输入一串正整数,正整数之间用空格键分开,请建立一个哈夫曼树,以输入的数字为叶节点,求这棵哈夫曼树的带权路径长度。 【输入形式】  首先输入正整数的个数,然后接下来为接下来的正整数,正整数个数不超过...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,729
精华内容 2,291
关键字:

哈夫曼带权路径长度