精华内容
下载资源
问答
  • 在一批数中, 选择两个最小的数字,用一个类似于树杈的“树枝”连接上两个最小的数。在顶点处计算出这两个数字的和 并写在上面。然后再比较剩下的数字和这个和的大小,再取出两个最小的数字进行排列
  • 哈夫曼树带权路径长度怎么计算

    万次阅读 2021-01-17 13:41:58
    哈夫曼带权路径长度是什么?1.的路径长度的路径长度是从树根到中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。2.带权路径长度(Weighted Path Length of Tree,...

    哈夫曼树的带权路径长度是什么?

    1.树的路径长度

    树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。

    2.树的带权路径长度(Weighted Path Length of Tree,简记为WPL)

    结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。

    结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。

    树的带权路径长度(Weighted Path Length of Tree):定义为树中所有叶结点的带权路径长度之和,通常记为:

    其中:

    n表示叶子结点的数目

    wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。

    树的带权路径长度亦称为树的代价。

    3.最优二叉树或哈夫曼树

    在权为wl,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。

    【例】给定4个叶子结点a,b,c和d,分别带权7,5,2和4.构造如下图所示的三棵二叉树(还有许多棵),它们的带权路径长度分别为:

    (a)WPL=7*2+5*2+2*2+4*2=36

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

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

    其中(c)树的WPL最小,可以验证,它就是哈夫曼树。

    注意:

    ① 叶子上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树。

    ② 最优二叉树中,权越大的叶子离根越近。

    ③ 最优二叉树的形态不唯一,WPL最小

    怎么求哈夫曼的带权路径长度

    【问题描述】

    已知输入两行正整数,第二行正整数之间用空格键分开,请建立一个哈夫曼树,以输入的数字为叶节点,求这棵哈夫曼树的带权路径长度。

    【输入形式】

    首先第一行为输入正整数的个数,然后接下来的一行正整数,代表叶结点,正整数个数不超过1000个

    【输出形式】

    输出相应的权值

    【样例输入】

    5

    4 5 6 7 8

    【样例输出】

    69

    关于哈夫曼树——

    1、 路径长度

    从树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称做路径长度。

    0736fa226baf6f5bfd6c45ca460a7fb5.png

    1、 树的路径长度

    路径长度就是从树根到每一结点的路径长度之和。

    9b3964157fb1d574e8c4b450f9d5c1fd.png

    1、 哈夫曼树:

    带权路径长度WPL(Weighted Path Length)最小的二叉树,也称为最优二又树。

    例: 上图的WPL=1*5 + 2*15 + 3*40 + 4*30 + 4*10= 315

    先了解通过刚才的步骤,我们可以得出构造哈夫曼树的算法描述。

    1、根据给定的n个权值{w[1],w[2],…,w[n]}构成n棵二叉树的集合F={T[1],T[2],…T[n]}, 其中每棵二叉树T[i];中只有一个带权为w[i]的根结点,其左右子树均为空。

    2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的。二叉树,且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和,

    3、在F中删除这两棵树,同时将新得到的二义树加入F中。

    4重复2和3步骤,直到F只含一棵树为止。这棵树便是哈夫曼树。

    结合例题说明一下这个算法

    940e4d5c09f0f1b70e2657fe378179e5.png

    99f58a9808e75a5fb9fb6d56da674217.png

    27b009a9c50387070ccd211631277e0e.png

    那么可以由上面的哈夫曼树计算出最小带权路径长度

    WPL = 1*9 + 2*5 + 3*2 + 4*1 + 4*2 =37

    另外还可以有另外一个方法,结合算法描述仔细观察发现最小带权路径长度为非叶子结点的和 ,即

    WPL= 19 + 10 +5 +3=37

    至于算法的正确性,一下子也想不到什么好的办法来证明,不过应该是可以逻辑推导过来的。

    那么要实现这段程序,由上面的算法描述图我们已经知道差不多了,主要分为三步:

    一、排序,直到数组中只有一个数则退出

    二、最小两个数加起来,即为非叶子节点,累加到累加器中

    三、把最小两个数加起来作为一个新的值保存在数组中,去掉最小两个值,跳回第一步

    #include《stdio.h》

    #include《stdlib.h》 //qsort();

    #define N 1010

    int rising(const void *a, const void *b)

    {

    return *(int*)a - *(int*)b;

    }

    int main()

    {

    int leaf[N] = {0}, n, i, sum = 0;

    scanf(“%d”, &n);

    for(i=0; i《n; i++)

    scanf(“%d”, leaf+i);

    for(i=0; i《n-1; i++)

    {

    qsort(leaf+i, n-i, sizeof(leaf[0]), rising); //排序并剔除已使用的叶结点

    leaf[i+1] += leaf[i]; //合并两个最小的叶结点成一新的节点(放在leaf[i+1]中)

    sum += leaf[i+1]; //总路径长 = 所有非叶结点之和

    }

    printf(“%d\n”, sum);

    return 0;

    }

    打开APP阅读更多精彩内容

    点击阅读全文

    展开全文
  • 需要用这些叶结点生成哈夫曼,根据哈夫曼的概念,这些结点有权值,即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

    展开全文
  • 哈夫曼:一类带权路径最短的。用于通讯及数据传送中构造传输效率最高的二进制编码(哈夫曼编码),用于编程中构造平均执行时间最短的最佳判断过程。节点之间的路径长度:从一个节点到另一个节点之间的分支数目。...

    哈夫曼树:一类带权路径最短的树。用于通讯及数据传送中构造传输效率最高的二进制编码(哈夫曼编码),用于编程中构造平均执行时间最短的最佳判断过程。节点之间的路径长度:从一个节点到另一个节点之间的分支数目。

    树的路径长度:从树的根到树中每一个节点的路径长度之和;
    下面以【5,7,10,12,18,20,28】为例(美团笔试题):
    在这里插入图片描述

    展开全文
  • #include<stdio.h> #include<queue> using namespace std; priority_queue<int, vector<int> ,greater<int>> q; int main() { int n; while (scanf("%d", &... whi...
  • 哈夫曼带权路径长度=所有叶子节点的带权路径长度和 应该也知道还有另一种算法 哈夫曼带权路径长度=所有非叶子结点的权值和 ![图片说明](https://img-ask.csdn.net/upload/201604/04/1459752161_872418.jpg...
  • 哈夫曼 带权路径长度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; 证明如下:(证明并不充分 详细点的证明和...
  • 的所有叶子结点的带权路径长度之和,称为带权路径长度,英文缩写为 `WPL`,从百度百科中得到的信息为 “带权路径长度(weighted path length of tree)是2018年公布的计算机科学技术名词”,这就有点奇怪...
  • 30)个字符组成,字符在电文中出现的频度(权值)为w1w2…wn,试根据该权值序列构造哈夫曼,并计算该带权路径长度。 问题输入 一组数据,第1行为n的值,第2行为n个整数,表示字符的出现频度。 问题输出 ...
  • 本文用C++采用顺序存储实现求哈夫曼(即最小生成)的带权路径长度努力下面来了解一下哈夫曼的构造以及如何求带权路径长度:哈夫曼带权路径长度最小的哈夫曼哈夫曼的顺序存储【问题描述】已知输入一串...
  • 注意:哈夫曼并不唯一,但带权路径长度一定是相同的。二叉树:每个结点最多含有两个子树的称为二叉树。定理:对于具有n个叶子结点的哈夫曼,共有2n-1个结点。 哈夫曼介绍1哈夫曼的定义哈夫曼(Huffman),又...
  • 哈夫曼带权路径长度的算法

    千次阅读 2021-05-10 20:06:24
    计算方法: ①先对集合中的结点按照权值从小到大排。 ②选两个权值最小的结点,将它们...⑤计算的时候,只计算那些初始权值里面有的值,把它们的【权值】*【权值到根节点的距离】,再全部相加得到带权路径长度。 ...
  • 给定n个权值(权值均是大于0的正整数),构造赫夫曼HT,并求出赫夫曼HT的带权路径长度。 注意:构造赫夫曼HT时,在将2棵二叉树合并成一棵新的二叉树时,将根结点权值小的用作左子树! 输入 先输入权值的个数n(n...
  • 哈弗曼带权路径长度

    千次阅读 2020-03-19 22:56:53
    最近刷题刷到了这一题,此...需要用这些叶结点生成哈夫曼,根据哈夫曼的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入描述: 输入有多组数据。 每组第一行输入一个数n,接着...
  • 首先什么是哈夫曼:哈夫曼,又称最优二叉树,是一类带权路径长度最短的。也就是根节点到节点的中的长度最小,当然条件就是,每条路径都是有权重的,所谓带权路径长度,就是中所有的叶结点的权值乘上其到...
  • C语言自动计算哈夫曼带权路径长度: #include<stdio.h> #include<stdlib.h> int cmp(const void *a,const void *b) { return *(int*)a-*(int *)b; } int main() { int n,W[1001]; while(scanf("%...
  • 哈夫曼带权路径长度

    千次阅读 2020-02-18 15:28:38
    哈夫曼带权路径长度 哈夫曼是带权路径最小的一种特殊二叉树,所以也称最优二叉树。 在这里不讨论基本概念如如何计算路径等,而只着重于的创建,具体过程让我们举例而言。 其基本的原理为:将所有节点一开始...
  • 需要用这些叶结点生成哈夫曼,根据哈夫曼的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过...
  • 思想: 先构建一个线性表,将的结点存入,然后对的结点进行升序排序,这样就保证了线性表的前两...而寻找带权路径长度可以使用递归的方法。 代码: public class Main { public static void main(String[] args) {
  • 带权路径长度

    千次阅读 2019-07-24 16:37:36
    从根节点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度
  • 所有非叶节点的权值之和=带权路径长度(WPL) 题目描述 哈夫曼,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼,根据哈夫曼的概念,这些结点有权值,即weight,题目需要输出所有结点的值...
  • 哈夫曼 题目描述 哈夫曼,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼,根据哈夫曼的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和的最小值。 输入描述...
  • void WPL() 计算带权路径长度 所选实例: 所选实例 创建哈夫曼 步骤: 假设有n个权值,则构造出的哈夫曼有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼的构造规则为: (1) 将w1、w2、...
  • 带权路径长度WPL 哈夫曼构造 哈夫曼性质 哈夫曼编码 试题
  • 二叉树的带权路径长度: 每个叶结点的深度与权值之积德总和。 方法:先序遍历或层次遍历 结点类型定义: typedef struct BiTNode{ int weight; struct BiTNode *lchild,*rchild; }BiTNode,BiTree; 基于先序: ...
  • 哈夫曼带权路径长度

    万次阅读 2018-08-28 04:37:41
    带权路径长度(Weighted Path Length of Tree):定义为中所有叶结点的带权路径长度之和。 结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。 哈夫曼是一种带权路径长度最短的二叉树,也...
  • 设计一个算法,计算 Huffman 带权路径长度。 #include<stdio.h> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,465
精华内容 4,586
关键字:

树的带权路径长度

友情链接: 2866754FFTConv.rar