精华内容
下载资源
问答
  • 带权路径长度

    2020-12-15 11:36:37
    给定n个权值作为n个叶子结点,构造哈夫曼树, 求其带权路径长度。 二、分析 带权路径长度得计算方法有两种:第一是第一法,第二是等于各个非叶子结点的权值之和。 这里我们用方法二计算,但是按照老方法,先构造一个...

    一、题目

    给定n个权值作为n个叶子结点,构造哈夫曼树, 求其带权路径长度。

    二、分析
    带权路径长度得计算方法有两种:第一是定义法,第二是等于各个非叶子结点的权值之和。
    这里我们用方法二计算,但是按照老方法,先构造一个哈夫曼树,之后再来计算会超时,所以这里我们不构造。可是对每次结果进行排序得话,再来选取最小得两个权值,函数会超时。所以我有点无能为力。然后在百度上搜索了一下,发现很多人都是使用优先队列做出来来的。所以我查阅了一下关于优先队列得知识。如下:

    在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。
    优先队列的时间复杂度为O(logn),n为队列中元素的个数,其存取都需要时间。
    在默认的优先队列中,优先级最高的先出队。默认的int类型的优先队列中先出队的为队列中较大的数。

    定义:priority_queue<Type, Container, Functional>
    Type 就是数据类型,Container 就是容器类型(Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector),Functional 就是比较的方式。
    当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大顶堆。
    一般是:
    //升序队列,小顶堆 priority_queue <int,vector,greater > q;
    //降序队列,大顶堆priority_queue <int,vector,less >q;
    数据结构:优先队列,小顶堆。
    优先访问小者。
    三、算法实现
    (主要代码)

    typedef unsigned long Lu;
    int main()
    {
        int n,i;
        Lu sum,a,b,y,x;
        while(scanf("%d",&n)==1)
        {
            sum=0;
            priority_queue <Lu,vector<Lu>,greater<Lu> > q;//小丁堆得使用
            while(!q.empty())
                q.pop();
            for(i=1;i<=n;i++)
            {
                cin>>x;
                q.push(x);
            }
            for(i=2;i<=n;i++)
            {
                a=q.top();
                q.pop();
                b=q.top();
                q.pop();
                y=a+b;
                sum=(sum+y)%1000000007;//计算带权路径长度
                q.push(y);
            }
            printf("%lu\n",sum%1000000007);
     
        }
        return 0;
    }
    

    四、算法分析
    算法分析:优先队列的时间复杂度为O(logn),n为队列中元素的个数,其存取都需要时间。计算过程为O(N)。故其时间复杂度为O(N)。
    空间复杂度:O(N).

    展开全文
  • 树的带权路径长度WPL 哈夫曼树构造 哈夫曼树性质 哈夫曼编码 试题

    带权路径长度

    在这里插入图片描述

    树的带权路径长度WPL

    在这里插入图片描述

    哈夫曼树

    在这里插入图片描述

    哈夫曼树构造

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    哈夫曼树性质

    在这里插入图片描述

    哈夫曼编码

    在这里插入图片描述
    固定长度编码
    在这里插入图片描述
    可变长编码
    在这里插入图片描述
    前缀编码
    在这里插入图片描述
    在这里插入图片描述
    固定长度编码、可变长编码、前缀编码、哈夫曼编码
    在这里插入图片描述
    思维倒图
    在这里插入图片描述


    试题
    在这里插入图片描述
    在这里插入图片描述


    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 带权路径长度:结点具有权值,从该结点到根之间的路径长度乘以结点的权值,就是该结点的带权路径长度。 叶子结点的带权路径长度:从叶结点到根之间的路径长度(所在层数-1)乘以叶结点的权值。 树的带权路径...

    思路:层次遍历

    带权路径长度:结点具有权值,从该结点到根之间的路径长度乘以结点的权值,就是该结点的带权路径长度。

    叶子结点的带权路径长度:结点到根之间的路径长度(所在层数-1)乘以结点的权值。

    树的带权路径长度(WPL):树的所有叶子结点的带权路径长度之和。

    树的带权路径长度记为WPL = (W1*L1 + W2*L2 + W3*L3 + ... + Wn*Ln),N个权值Wi(i = 1, 2, ...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i = 1, 2, ...n)。

    随便复习哈夫曼树:

    可以证明哈夫曼树的WPL是最小的。WPL是衡量一个带权二叉树优劣的关键。无论如何,对于n个带权节点,可以用他们作为叶节点构造出一颗最小WPL值得树,并称满足这个条件的二叉树为哈夫曼树。

    【例】给定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最小,可以验证,它就是哈夫曼树。

    #include <iostream>
    #include <queue>
    using namespace std;
    
    class TreeNode{
    private:
    	char val;
    	TreeNode* left;
    	TreeNode* right;
    public:
    	//二叉树的初始化函数 
    	TreeNode* Create_TreeNode(){
    		TreeNode* T = new TreeNode;
    		char ch;
    		cin >> ch;
    		if (ch == '#'){                                                  //“#”是结束标志 
    			T = NULL;
    		}else{
    			T->val = ch;                                               //对当前结点初始化 
    			T->left = Create_TreeNode();                            //递归构造左子树 
    			T->right = Create_TreeNode();                            //递归构造右子树 
    		}
    		return T;
    	}
    
    	int WPL(TreeNode* root) {
    		queue<TreeNode*> que;//处理数据队列  
    		vector<int> temp;// 存储每一层数据  
    		 
    		TreeNode* last = root;
    		TreeNode* nLast = root;
    		que.push(root);
    		int level = 1;	//level代表层数 
    		int sum = 0; //带权路径长度之和    
    		while (!que.empty()){
    			TreeNode* proot = que.front();
    			que.pop();
    			temp.push_back(proot->val);
    			if (proot->left){ //左孩子非空入队
    				que.push(proot->left);
    				nLast = proot->left;
    			}
    			if (proot->right){ //右孩子非空入队
    				que.push(proot->right);
    				nLast = proot->right;
    			}
    			if (proot == last){ //队头指针是该层最后一个结点时 
    				level++;//层数加一
    				last = nLast;//最后一个结点指针下移到下一层的最后一个结点 
    				temp.clear();
    			}
    			if (proot->left == NULL && proot->right == NULL){
    				int weight = proot->val - '0';
    				sum += (level - 1)*weight; //层数level,该层的每个叶节点的带权路径长度 = (level - 1)*weight
    			}
    		}
    		return sum;
    	}
    };
    int main()
    {
    	cout << "请初始化二叉树:" << endl;
    	TreeNode Tree;
    	TreeNode* T1 = Tree.Create_TreeNode();
    
    	cout << "叶子节点的带权路径之和为:" << endl;
    	int wpl = Tree.WPL(T1);
    	cout << wpl << endl;
    	system("pause");
    	return 0;
    }
    



    展开全文
  • 层次:从树根开始定义,树根为第一层 深度:从根开始,向下累加 高度:从叶开始,向上累加 这里定义:树的高度/深度为数中结点最大层次数。...树的带权路径长度(WPL):所有叶结点带权路径长度之和.

    层次:从树根开始定义,树根为第一层

    深度:从根开始,向下累加
    高度:从叶开始,向上累加
    这里定义:树的高度/深度为数中结点最大层次数。

    A到B的路径长度:A到B所经过的边数(B层数 - A层数)
    树的路径长度:从根到树中每一结点的路径长度之和。
    在结点数目相同的二叉树中,完全二叉树的路径长度最短。

    带权路径长度到该结点的路径长度 × \times ×该结点的权值
    \qquad\qquad\qquad (A层数 - 1) × \times × A权值
    树的带权路径长度(WPL):所有叶结点带权路径长度之和
    WPL最小的数——Huffman树

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

    万次阅读 多人点赞 2017-11-08 13:55:38
    哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。下面用一幅图来说明。 它们的带权路径长度分别为: 图a: WPL=5*2+7*2+2*2+13*2=54 图b: WPL=5*3+2*3+7*2+13*1=48 可见,...
  • 题目:二叉树的带权路径长度(WPL)是二叉树中所有叶节点的带权路径长度之和。给定一颗二叉树T,采用二叉链表存储,节点结构为 left weight right 试设计求T的WPL的算法 分析: 我们求带权路径长度,既需要知道叶...
  • 哈夫曼树 和 树的带权路径长度

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

    千次阅读 2019-07-24 16:37:36
    从根节点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度
  • 带权路径长度(c++优先队列)

    千次阅读 2018-09-08 14:02:12
    思路:本题是求带权路径长度,可以用常规的构造哈夫曼树求带权路径长度;此外带权路径长度还是哈夫曼树所有非叶子节点的和;本题我采用的是通过求所有非叶子节点的和来就带权路径长度; 第一次的代码如下: #...
  • 常用操作: 哈夫曼树带权路径长度
  • 设计算法求二叉树的带权路径长度(WPL) 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。 队列的基本操作以严蔚敏编写的教材为准。 基于层次遍历的算法: int WPL_LevelOrder (BiTree T) { ...
  • 二叉树计算带权路径长度(WPL)的算法 更多内容请访问点击我的主页 题目 : 二叉树的带权路径长度是二叉树中所有叶子结点的带权路径长度之和。给定二叉链表的存储的结点结构为 left weight right weight...
  • 求二叉树的带权路径长度问题

    千次阅读 2019-07-02 00:39:36
    求二叉树的带权路径长度问题问题中的名词解释1 二叉树定义2 二叉树的带权路径长度问题解决方法1 先序遍历2 层次遍历个人总结 问题中的名词解释 1 二叉树定义 二叉树是n(n>=0)个节点的有限集合: 1 或者为空...
  • 哈夫曼树带权路径长度

    万次阅读 多人点赞 2018-08-13 16:24:51
    可见,图b的带权路径长度较小,我们可以证明图b就是哈夫曼树(也称为最优二叉树)。   二. 怎么生成和计算? 1. 总结 ①先对权值从小到大排序。 ②选两个最小的加起来成为一个新结点,而这两个最小的值是新结点...
  • 给定n个权值(权值均是大于0的正整数),构造赫夫曼树HT,并求出赫夫曼树HT的带权路径长度。 注意:构造赫夫曼树HT时,在将2棵二叉树合并成一棵新的二叉树时,将根结点权值小的用作左子树! 输入 先输入权值的个数n(n...
  • 哈夫曼树的带权路径长度=所有叶子节点的带权路径长度和 应该也知道还有另一种算法 哈夫曼树的带权路径长度=所有非叶子结点的权值和 ![图片说明](https://img-ask.csdn.net/upload/201604/04/1459752161_872418.jpg...
  • 注意:哈夫曼树并不唯一,但带权路径长度一定是相同的。 二叉树:每个结点最多含有两个子树的树称为二叉树。 定理:对于具有n个叶子结点的哈夫曼树,共有2n-1个结点。 哈夫曼树介绍 1哈夫曼树的定义 哈夫曼...
  • 哈夫曼编码计算带权路径长度问题

    千次阅读 2017-10-26 10:09:39
    哈夫曼树,又称最优二叉树,是一类带权路径长度最短的树。  也就是根节点到节点的中的长度最小,当然条件就是,每条路径都是有权重的,  所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的 ...
  • 哈夫曼树与带权路径长度

    万次阅读 多人点赞 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之中选取...
  • 求二叉树带权路径长度(WPL) 简介:*树的带权路径长度(Weighted Path Length of Tree,简记为WPL)*二叉树的带权路径长度是每个叶子节点深度(高度)与其指定权重的乘积总和。 算法思想:对于求带权路径长度我们...
  • 3766. 二叉树的带权路径长度 原题传送:AcWing 3766. 二叉树的带权路径长度 二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和,也就是每个叶结点的深度与权值之积的总和。 给定一棵二叉树 TTT ,请...
  • 若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树,则其带权路径长度是? 哈夫曼树,每次取根节点最小的2个(最开始每个节点单独构成树,所有节点组成森林)合并,最终形成一个二叉树 带权路径长度=sum(叶子...
  • 笔试题:哈夫曼编码{4,9,2,7,5,12}的带权路径长度 解决思路: 首先构造哈夫曼树 在使用WPL=(W1*L1+W2*L2+W3*L3+…+Wn*Ln)计算带权路径长度 实现: 构造哈夫曼树: 每次取出最小的两个数构造第一层,在给出的...
  • 带权路径长度 hnust数据结构

    千次阅读 2017-07-18 15:45:45
    问题 U: 带权路径长度 时间限制: 2 Sec 内存限制: 128 MB 提交: 268 解决: 48 [提交][状态][讨论版] 题目描述 给定n个权值作为n个叶子结点,构造哈夫曼树, 求其带权路径长度。 输入 输入由...
  • 带权路径长度 任务描述 给定N个权值作为N个叶子结点,构造哈夫曼树,求其带权路径长度 输入 输入由多组数据组成。 每组数据分成两行。第一行仅一个整数n(2<=n<=100000)。第二行有n个空格分开的权值,...
  • 二叉树的带权路径长度: 每个叶结点的深度与权值之积德总和。 方法:先序遍历或层次遍历 结点类型定义: typedef struct BiTNode{ int weight; struct BiTNode *lchild,*rchild; }BiTNode,BiTree; 基于先序: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,432
精华内容 5,772
关键字:

带权路径长度