精华内容
下载资源
问答
  • 树的带权路径长度(Weighted Path Length of Tree,简记为WPL)  结点的权:在一些应用中,赋予树中结点的一个 有某种意义的实数。  结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。  树的...

    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最小

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

    万次阅读 多人点赞 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

    展开全文
  • 哈夫曼结构和带权路径长度计算

    万次阅读 多人点赞 2017-11-08 13:55:38
    什么是哈夫曼呢? 哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。下面用一幅图来说明。...可见,图b的带权路径长度较小,我们可以证明图b就是哈夫曼(也称为最优二叉树)。 哈夫曼构建教

    什么是哈夫曼树呢?

    哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。下面用一幅图来说明。


    它们的带权路径长度分别为:

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

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

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

    哈夫曼树构建教程

    例:对于给定的一组权值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.....)


    展开全文
  • 所有非叶节点的权值之和=带权路径长度(WPL) 题目描述 哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值...

    先验知识——哈夫曼树的一个性质

    所有非叶节点的权值之和=带权路径长度(WPL)

    题目描述

    哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和(没读明白什么意思,但看样例应该是WPL)。

    输入输出格式

    输入描述

    输入有多组数据。每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000)。

    输出描述

    输出权值。

    输入输出样例

    输入样例

    5
    1 2 2 5 9

    输出样例

    37

    AC代码

    #include <bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        int n = 0;
        while(scanf("%d",&n) != -1)
        {
            int ans = 0;
            int weight = 0;
            int tp1 = 0;
            int tp2 = 0;
            int num = 0;
            priority_queue<int,vector<int>,greater<int>> myQ;
            // 构造小根堆
            for(int i=0;i<n;i++)
            {
                scanf("%d",&weight);
                myQ.push(weight);
            }
            while(myQ.size() > 1)
            {
                // 选择两个权值最小的结点
                tp1 = myQ.top();
                myQ.pop();
                tp2 = myQ.top();
                myQ.pop();
                num = tp1+tp2;
                ans += num;
                // 生成新结点
                myQ.push(num);
            }
            printf("%d\n",ans);
        }
        return 0;
    }
    

    总结

    1. priority_queue这个容器的数据结构是堆,默认是大根堆。priority_queue<int,vector,greater>这个样子声明是小根堆,可以快速的找到最小的结点,时间复杂度为对数阶。用在本题是为了高效率的寻找权值最小的两个元素(参考哈夫曼树的构造算法)。
    2. 参考本文开头提到的哈夫曼树的性质,解决该题不需要真正构造出哈夫曼树。
    展开全文
  • 在做一道编程提示遇到的,学习了一位博主的...所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WP
  • 数据结构之哈夫曼

    2020-12-18 19:46:34
    一、什么是哈夫曼树 基本介绍 1.给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度1(wpl)达到最小,称这样的二叉树为最优叉树。...3.带权路径长度最短的树,那么树的带权路径长度是什么? 什
  • 什么是哈夫曼

    2021-01-29 09:30:23
    给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。 哈夫曼树带权路径长度最短的树,权值较大的结点离根近。 相关概念的说明: ...
  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树带权路径长度最短的树,权值较大的结点离根较近 哈夫曼树又称...
  • 数据结构—哈夫曼树(Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和...树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL(weighted path length
  • 设二叉树有n个叶子结点,每个叶子结点的权重为Wk,从根节点到每个叶子结点的长度为Ik,则所有叶子结点带权路径长度( Wk * Ik)的和为该树的带权路径长度之和(WPL)。 WPL = ∑nk=1 Wk * Ik; 这些只是概念上的东西...
  • 树的带权路径长度为树中所有叶子结点的带权路径长度之和,通常记作WPL。 对于哈夫曼树而言,其有一个非常显著的特点 ------- 没有度为1的结点.这类树又称严格的二叉树,对于这样的二叉树,根据其特点,如果
  • 树的带权路径长度(WPL)为树中所有叶子结点的带权路径长度之和。 例如下面的二叉树,有5个带权结点,它WPL= 5×3+15×3+40×2+30×2+10×2=220 构造哈夫曼树 构造哈夫曼树,即构造一个带权路径长度最小的二...
  • 哈夫曼及其实现

    2019-08-08 11:48:32
    给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树带权路径长度最短的树,即权值较大的结点离根较近。 哈夫曼树...
  • Hffman Tree

    2017-12-11 10:55:43
    一、概念 1、什么是Huffman Tree? 又称赫夫曼树、霍夫曼树、哈夫曼树、最优二叉树等,一类带权路径长度最短的树。 2、路径与路径长度 ...树的带权路径长度为树中所有叶子节点的带权路径长度之和。
  • 给定n个权值作为n个叶子节点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。哈夫曼树带权路径长度最短的树,权值较大的节点距离根节点较近。 基本术语 路径和...
  • 哈夫曼

    千次阅读 2020-01-29 12:00:46
    文章目录举个栗子哈夫曼树的基本术语路径树的路径长度权结点的带权路径长度树的带权路径长度 本篇文章将讲述哈夫曼树的相关内容。 举个栗子 既然要学哈夫曼树,我们就得知道什么是哈夫曼树,哈夫曼树的作用是什么。...
  • 哈夫曼及图遍历

    2021-06-21 21:58:36
    1.哈弗曼树的构建 概念1:什么是路径? 在一棵树中,从一个结点到另一个结点所经过的所有结点,被我们称为两个结点之间的路径。 概念2:什么是路径长度?...概念4:什么是树的带权路径长度? 在一棵树中.
  • 赫夫曼

    2017-08-07 15:39:51
    赫夫曼编码主要用于数据压缩(无损压缩) 什么是赫夫曼树? ...树的带权路径长度:WPL(Weight Path Length)树中所有叶子结点的带权路径长度之和 WPL的值越小,说明构造出来的二叉树的性能越优
  • 树的带权路径长度为树中所有叶子结点的带权路径长度之和,记为:WPL= 其中,n为带权叶子结点数目,wk 为叶子结点的权值,lk 为叶子结点到根的路径长度。 构造最优二叉树的方法 构造最优二叉树的哈夫曼算法如下...
  • Huffman

    2015-11-16 23:48:51
    哈夫曼(HUFFMAN) 树和哈夫曼编码。哈夫曼编码哈夫曼树的一个应用。哈夫曼编码应用广泛,如 JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树, ...树的带权路径长度记为
  • 哈夫曼及哈夫曼编码

    千次阅读 多人点赞 2018-09-29 18:25:25
    哈夫曼树 哈夫曼树,最优二叉树,带权路径长度(WPL)最短的树。它没有度为1的点,一棵严格的二叉树(满二叉树)。 何谓‘带权路径长度’ ...树的带权路径长度:树中所有叶子结点的带权路径之和W...
  • 1.4 什么是树的带权路径长度?2、哈夫曼树2.1 概念2.2 图解构造哈夫曼树2.3 代码实现3、哈夫曼编码 1、先掌握几个概念   先听一遍哈夫曼树的概念:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径...
  • java 实现哈夫曼

    千次阅读 2019-03-01 23:09:08
    一、 什么是哈夫曼树 要理解什么是哈夫曼树,首先要理解几个概念 路径:从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。...树的带权路径长度:树的所有结点的带权路径之和(...
  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树带权路径长度最短的树,权值较大的结点离根较近。 简而言之...
  • 哈夫曼(HUFFMAN)树和哈夫曼编码属于数据结构...所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为 WP
  • 1、什么是哈夫曼树 ... WPL树的带权路径长度: wi表示权值 li表示树的深度 例如: 上面三棵树的带权路径长度分别: WPL(1) = 4*2+7*3+5*3+2*1=46 WPL(2)=7*2+5*2+2*2+4*2=36 WPL(3)=7*1+5*...

空空如也

空空如也

1 2 3 4 5 ... 13
收藏数 243
精华内容 97
关键字:

树的带权路径长度是什么