精华内容
下载资源
问答
  • 哈夫曼树带权路径长度是什么?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阅读更多精彩内容

    点击阅读全文

    展开全文
  • 哈夫曼树:一类带权路径最短的树。用于通讯及数据传送中构造传输效率最高的二进制编码(哈夫曼...树的路径长度:从树的根到树中每一个节点的路径长度之和; 下面以【5,7,10,12,18,20,28】为例(美团笔试题): ...

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

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

    展开全文
  • 从根结点到叶子结点的路径长度乘以叶子节点权值,得到的值为该节点的带权路径长度,中所有叶子节点的带权路径长度之和称为该的带权路径长度和。给定N个结点和它们的权值,以这N个结点为叶子节点构造的带权路径...

    1.哈夫曼树概念

    一棵树中,从任意一个结点到达另一个结点的通路叫做路径,该路径包含的边的个数称为路径长度,每个结点带有的表示某种意义的值成为权值。从根结点到叶子结点的路径长度乘以叶子节点权值,得到的值为该节点的带权路径长度,树中所有叶子节点的带权路径长度之和称为该树的带权路径长度和。给定N个结点和它们的权值,以这N个结点为叶子节点构造的带权路径长度和最小的二叉树,就是哈夫曼树。

    2.C语言实现给定结点,求哈夫曼树的带权路径长度和

    哈夫曼树带权路径长度和求解算法:

    (1)所有结点权值放入集合K,并始终保持K中元素按从小到大排序(使用优先队列priority_queue)。

    (2)if K中结点数目不小于1,取前两个元素a,b相加,并弹出前两个元素a,b,将所得的和插入集合K(插入后K中元素顺序依然保持从小到大);if K中结点数目只有1,这个就是根节点的权值。

    (3)所有中间结点权值相加(即把所有a+b求和),即为所求哈夫曼树带权路径长度和(根据(路径长度*权值)求和的公式很容易推出来)

    注意:使用优先队列,即堆数据结构,使得我们可以以O(logn)的时间复杂度就取出集合中最小的前两个元素a,b,具体原理,可以参考堆结构的相关知识。

    #include<queue>
    #include<functional>
    priority_queue<int, vector<int>, greater<int>> Q;
    int main() {
    	int n;
    	while (scanf_s("%d", &n) != EOF) {
    		while (!Q.empty()) Q.pop();
    		for (int i = 0; i < n; i++) {
    			int tmp;
    			scanf_s("%d", &tmp);
    			Q.push(tmp);
    		}
    		int ans = 0;
    		while(Q.size()>1){
    		
    				int a, b;
    				a = Q.top();
    				Q.pop();
    				b = Q.top();
    				Q.pop();
    				ans += (a + b);
    				Q.push(a + b);
    		}
    		printf("%d", ans);
    	}
    	return 0;
    }


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

    万次阅读 2018-08-28 04:37:41
    树的带权路径长度(Weighted Path Length of Tree):定义为树中所有叶结点的带权路径长度之和。 结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。 哈夫曼树是一种带权路径长度最短的二叉树,也...

    树的带权路径长度(Weighted Path Length of Tree):定义为树中所有叶结点的带权路径长度之和。
    结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。

    哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。

     

    哈夫曼树构建教程 https://blog.csdn.net/xueba8/article/details/78477892

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

    解:1、首先我们对这一组数字进行排序。规则是从小到大排列(题目已排序好)。

          2、在这些数中 选择两个最小的数字(哈夫曼树是从下往上排列的)写在纸上。如下图所示

          3、用一个类似于树杈的“树枝”连接上两个最小的数。在顶点处计算出这两个数字的和 并写在上面。然后再比较剩下的数字和这个和的大小,再取出两个最小的数字进行排列

     

          4、如上图中30,25的和为55,已经大于36,49.所以这个时候开始有分支,用36,49再构造一个分支,如下图。

     

        5、最后将分支合并成一个二叉树,如下图

    6、这样,二叉树结构就构建好了。

    带权外部路径长度计算;

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

    (385的权重为0,216和166权重为1.....)

    展开全文
  • 在准备软考的过程中遇到哈夫曼树题型,有些...设二叉树具有N个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度:WPL=w1l1+w2l2+…+wklk 其中wk为第K个...
  • 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过...
  • 的路径长度是从树根到中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。 2. 带权路径长度(Weighted Path Length of Tree,简记为WPL)  结点的权:在一些应用中,赋予...
  • 所有非叶节点的权值之和=带权路径长度(WPL) 题目描述 哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值...
  • 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和的最小值。 输入描述: 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶...
  • 带权路径:每个叶子结点都有权值,对于某叶子结点来说,它的带权路径就是“结点权值*从根节点到该结点的路径长度”。 ②哈夫曼树的构造方法:两个权值最小的叶子结点作为兄弟去构成一个非叶节点。(该父亲非叶...
  • 哈夫曼树中的名词意思:(ps:本想画个图的不知这上面怎么...树带权路径长度:所有叶子节点的带全路径长度之和树带权路径长度:所有叶子节点的带全路径长度之和。 建立哈夫曼树:单独将数组中的每个值作为一个节点,依
  • 题目所描述的有点问题,其实是叶节点的路径与权值乘积之和,即带权路径长度! 用到了c++中小顶堆的创建方法,优先队列。 定义:priority_queue<Type, Container, Functional> Type 就是数据类型,Container ...
  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。要构成哈夫曼树,值比较大的叶子节点高度越低越好。 (1) 将n个权值看出n...
  • 问题 C: 哈夫曼树 ...需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入 输入有多组数据。 每组第一行输入一个数n,接着输...
  • 设扩充二叉树具有m个带权值的外部节点,那么从根节点到各个外部节点的路径长度与相应结点权值的乘积的,叫做扩充二叉树的带权的外部路径长度。。记作WPL。。。(摘抄自算法与数据结构课本)。 而关于哈夫曼树的应用...
  • 根据网上的相关资料,通过构造哈夫曼树求解最优二叉树所有叶子结点的带权路径长度之和   # include #include #define maxsize 30; /*  霍夫曼树求解最佳二叉树  完成时间:2015-7-10 */ typedef struct ptree { ...
  • 带权路径长度

    2020-12-15 11:36:37
    带权路径长度得计算方法有两种:第一是第一法,第二是等于各个非叶子结点的权值之和。 这里我们用方法二计算,但是按照老方法,先构造一个哈夫曼树,之后再来计算会超时,所以这里我们不构造。可是对每次结果进行...
  • 最近刷题刷到了这一题,此...需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入描述: 输入有多组数据。 每组第一行输入一个数n,接着...
  • 哈夫曼树带权最优二叉树)

    万次阅读 2018-05-24 19:52:34
    一、哈夫曼树 1、哈夫曼树简介 ...二叉树的路径长度是指由根结点到所有叶子结点的路径长度之和。如果二叉树中的叶子结点都有一定的权值,则可将这一概念拓展:设二叉树具有n个带权值的叶子结点,则从...
  • 树的带权路径长度:这棵树所有叶子结点的带权路径长度之和 2 哈夫曼树 带权路径长度最小的树 哈夫曼树可以不唯一,但是最小带权路径长度一定是唯一的 可以使用优先队列实现堆,例子如下: #include<stdio.h...
  • 4.树的带权路径长度:树中所有叶子节点的带权路径长度之和 哈夫曼树=带权路径长度最短的树(要么都比二叉树或者三叉树) 1.哈夫曼树权值越大的叶子越靠近根 2.具有相同带权节点的哈夫曼树不为一 步骤 1.构造森林全是...
  • 哈夫曼树及其应用 ...树的带权路径长度(WPL):定义为书中所有叶结点的带权路径长度之和。 最优二叉树或哈夫曼树 带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树。 结点的带权路径长度:结点到树根之
  • 数据结构-树(下)-哈夫曼树与哈夫曼编码(基础知识)哈夫曼树带权路径长度(WPL)哈夫曼树的构造哈夫曼编码 哈夫曼树 带权路径长度(WPL) 二叉树中所有叶结点的带权路径长度之和,其中n为叶节点数,根节点要叶...
  • 哈夫曼树定义:哈夫曼树又被称为最优二叉树,即树的所有叶子节点的带权路径长度之和最小。 树的所有节点的带权路径长度之和又被称为该树的带权路径长度之和哈夫曼树可能不唯一,但是带权路径长度之和的最小值却...
  • 哈夫曼树

    2021-02-07 15:28:26
      树的带权路径长度: 所有叶子结点的带权路径长度之和,记为 WPL (weighted path length)。   哈夫曼树: 给定 n 个权值作为 n 个叶子结点,构造一棵二叉树,若该树的带权路径长度 (wpl) 达到最小,称这样的...
  • 哈夫曼树及其编码

    2018-04-24 17:07:21
    1、定义树的带权路径长度(WPL) 将树的每一个节点附加一个权值,树中所有叶子节点的带权路径长度之和成为该树的带权路径长度。其计算公式如下:哈夫曼树 带权路径长度WPL最小的二叉树成为哈夫曼树(或最优二叉树)...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 526
精华内容 210
关键字:

哈夫曼树带权路径长度之和