精华内容
下载资源
问答
  • 2019-06-21 15:52:52

    定义

    给定一组具有确定权值的叶子节点,带权路径长度最小的二叉树就叫做哈夫曼树。

    特点

    1.权值越大的叶子节点越靠近根节点,而权值越小的叶子节点越远离根节点。
    2.只有度为0和2的节点,不存在度为1的节点。

    基本思想

    ⑴ 初始化:由给定的n个权值{w1,w2,…,wn}构造n棵只有一个根结点的二叉树,从而得到一个二叉树集合F={T1,T2,…,Tn};
    ⑵ 选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和;
    ⑶ 删除与加入:在F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到F中;
    ⑷ 重复⑵、⑶两步,当集合F中只剩下一棵二叉树时,这棵二叉树便是哈夫曼树。

    小提示

    计算最短带权路径一定要理清思路,思路最关键,每个人的代码可能不一样,但思路是殊途同归的,有bug的话对学程序的人来说就见怪不怪了,具体在代码中体会,话不多说,直接上代码。

    #include<bits/stdc++.h>
    using namespace std;
    
    typedef struct//哈夫曼树的存储表示
    {
        int weight;    					//权值
        int parent, lChild, rChild;    	//双亲及左右孩子的下标 
    }HTNode, *HuffmanTree;
    
    void Select(HuffmanTree hT, int n, int &s1, int &s2)//选择两个最小节点 
    {
        s1 = s2 = 0;
        int i;
        for(i = 1; i < n; ++ i)//选择两个未有双亲的节点 
    	{
            if(hT[i].parent == 0)
    		{
                if(0 == s1)
    			{
                    s1 = i;
                }
                else
    			{
                    s2 = i;
                    break;//后面一个for循环的标记 
                }
            }
        }
        if(hT[s1].weight > hT[s2].weight)//确保s1>s2 
    	{
            int t = s1;
            s1 = s2;
            s2 = t;
        }
        for(i+=1;i<n;++i)//选择s2即break 故从i+1开始选择两个最小节点 
    	{
            if(hT[i].parent==0)
    		{
                if(hT[i].weight < hT[s1].weight)
    			{
                    s2 = s1;
                    s1 = i;
                }
    			else if(hT[i].weight < hT[s2].weight)
    			{
                    s2 = i;
                }
            }
        }
        //cout<<s1<<" "<<s2<<"**"<<endl;
    }
    
    void CreateHufmanTree(HuffmanTree &hT)//构造哈夫曼树 
    {
        int n,m;
        cin>>n;
        m = 2*n - 1;
        hT = new HTNode[m + 1];
    	hT[0].weight=m;  // 0号节点用来记录节点数量 
        for(int i = 1; i <= m; ++ i)
    	{
            hT[i].parent = hT[i].lChild = hT[i].rChild = 0;//初始化 
        }
        for(int i = 1; i <= n; ++ i)
    	{
            cin >> hT[i].weight;    // 输入权值 
        }
        for(int i = n + 1; i <= m; ++ i)//建立过程 
    	{
            int s1, s2;
            Select(hT, i, s1, s2);
            hT[s1].parent = hT[s2].parent = i;
            hT[i].lChild = s1; hT[i].rChild = s2;    			//作为新节点的孩子 
            hT[i].weight = hT[s1].weight + hT[s2].weight;    	//新节点为左右孩子节点权值之和 
        }
        
    }
    
    int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth)//递归计算WPL 
    {
        if(hT[i].lChild == 0 && hT[i].rChild == 0)
    	{
            return hT[i].weight * deepth;
        }
        else
    	{
            return HuffmanTreeWPL_(hT, hT[i].lChild, deepth + 1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth + 1);
        }
    }
    
    int HuffmanTreeWPL(HuffmanTree hT)//计算WPL 
    {
        return HuffmanTreeWPL_(hT, hT[0].weight, 0);
    }
    
    void DestoryHuffmanTree(HuffmanTree &hT)//销毁哈夫曼树 
    {
        delete[] hT;
        hT = NULL;
    }
    
    int main()
    {
        HuffmanTree hT;
        CreateHufmanTree(hT);
        cout << HuffmanTreeWPL(hT) << endl;
        DestoryHuffmanTree(hT);
        return 0;
    }
    
    更多相关内容
  • 哈夫曼树求最短路径

    2018-12-06 12:51:07
    上机后的代码,内容为构建哈夫曼树,并求最短编码长度。
  • 二、完全二叉搜索 什么是二叉搜索? 左子树<根结点<右子。 什么是完全二叉树? 完美二叉树的子部分 的表示方法? 链表、数组(不涉及指针操作,但可能空间浪费比较严重) 题目:给定一串数列,...

    一、Tree Traversals Again

     

    二、完全二叉搜索树

    什么是二叉搜索树?
    左子树<根结点<右子树。

    什么是完全二叉树?

    完美二叉树的子部分

    树的表示方法?
    链表、数组(不涉及指针操作,但可能空间浪费比较严重)

    题目:给定一串数列,将它以完全二叉搜索树的层序遍历方式输出。

    核心算法:
     

    
    
    void solve (int ALeft , int ARight , int TRoot)
    {
        n = ARight - ALeft + 1;
        if (n==0)  return;
        L = GetLeftLength(n); //得到结点树为n的树其左子树结点的个数
        T[TRoot] = A[Aleft+L];
        LeftTRoot = TRoot*2+1;
        RightTRoot = LeftTRoot+1;
        solve(ALeft,ALeft+L-1,LeftTRoot);
        solve(ALeft+L+1,ARight,RightTRoot);
    
    }

    一个排序算法


    计算左子树的规模

     三、Huffman Codes(最优编码)

    最优编码不一定要通过哈夫曼算法得到!!!

    哈夫曼编码的特点

    1、最优编码——最长度(WPL)最小

    2、无歧义编码——前缀码:数据仅存在于叶子结点

    3、没有度为1的结点——满足1、2则必然有3.

    哈夫曼树的构造:每次把权值最小的两棵二叉树合并

    MinHeap H = CreateHeap(N);创建一个空的、容量为N的最小堆
    
    H = ReadData(N);  将f[]读入H—>Data[]中
    
    HuffmanTree T = Huffman (H);  //建立Huffman树
    
    int CodeLen = WPL( T , 0);
    
    
    int WPL(HuffmanTree T , int Depth)
    {    if( !T->Left && !T->Right)
            return (Depth * T->Weight);
    
        else //负责T一定有两个孩子
            return (WPL(T->Left , Depth-1)+WPL(T->Right , Depth));
    
    
    }

    四、最短路径问题

    最短问题的抽象:

    在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径。

    (一)无权图的单源最短路径算法

    void Unweighted( Vertex S)
    
    {        Enqueue( S,Q);
    
            while( !IsEmpty(Q)){
                V = Dequeue(Q);
                for(V的每一个邻接点W){
                    if( dist[W] == -1){
                        dist[W] = dist[V] + 1;
                        path[W] = v;
                        Enqueue(W , Q);
                    }
                }
            }
    }

    (二)有权图的单源最短路径

    Dijkstra算法

     

     

     (三)多源最短路算法

    方法一:直接将单源最短路算法调用|V|遍,T = O(|V|^3+|E|*|V|)——对于稀疏图效果好。

    方法二:Floyd算法   T = O(|V|^3)——对于稠密图效果好点

     

     

    展开全文
  • **描述:**哈夫曼编码是可变字长编码(VLC)的一种,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字。 **贪心策略:**把编码映射成二叉树,把频率高的字符分配给靠近根节点的叶节点,把频率低的字符...

    哈夫曼编码

    描述:哈夫曼编码是可变字长编码(VLC)的一种,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字。
    贪心策略:把编码映射成二叉树,把频率高的字符分配给靠近根节点的叶节点,把频率低的字符放置在远离根节点的叶节点。
    自底向上构造二叉编码树,由森林不断合并得到一棵二叉树。
    思路分析:为了便于找到频次最低的字符,哈夫曼算法建立一个以f为键值的优先队列Q,假设编码字符集中每一字符c的频率是f( c ).哈夫曼编码算法以自底向上的方式构造最优编码树T。

    • 一开始,每个字符构成只包含一个节点的树
    • 合并频率最低的两棵树,并产生一棵新树,其频率为合并的两棵树的频率之和,并将新树插入优先队列Q中。
    • 循环n-1次后,优先队列中只剩下一棵树,即最优二叉编码树。
    struct cmp{
    	bool operator()(connst int &x,const int &y){
    		return x>y ;
    	}
    };//定义有限对列比较函数
    double haffmanCoding(int n,int *freq){
    	int i,total = 0,sumFreq = 0,jointFreq ;
    	priority_queue<int,vector<int>,cmp> heap ;
    	for(int i=0;i<n;i++){
    		total += freq[i] ;  //频率总和
    		heap.push(freq[i]) ;
    	}//形成有限对列
    	while(heap.size()>1){ //循环选择对列中频次最少的两个元素合并
    		jointFreq = 0 ;   //合并两个节点的频率
    		for(int i=0;i<2;i++){   //删除频次最少的两元素
    			jointFreq += heap.top() ;
    			heap.pop() ;
    		}
    		sumFreq += jointFreq ;     
    		heap.push(jointFreq) ;   //优先队列中插入合并节点
    	}
    	return sumFreq/(1.0*total) ;   返回平均码长
    }
    //复杂度O(nlg(n))
    

    单源最短路径

    描述: 有向图G有n个顶点,给定每两个顶点的权值,权值为非负实数,如果权值为-1,表示没有边相连,默认第一个顶点为源。计算假设源可以到达任何一个顶点,从源到各顶点的最短路径长度。
    特征:最短路径的子路径也是源到相应顶点的最短路径。
    Dijstra算法
    在这里插入图片描述
    贪心策略:选择集合V-S中受限路径长度最短的顶点,并把相应顶点加入到S中,相应地最短路径树T叶增加一条边。
    在这里插入图片描述
    代码:

    #define INF 0x3f3f3f3f //预定义的充分大的数
    #define MaxV 100
    int preV[MaxV];  //最短路径树中的前驱节点信息表
    int visited[MaxV];  //结点是否加入S的标记表,0是为加入,1是加入
    void Dijkstra(int linkMatrix[][MaxV],int lowLR[MaxV],int numV,int beginV){
    	int i,j,min,newCost ;
    	memset(visited,0,sizeof(visited)) ;   //初始化,所有结点为加入
    	//开始结点beginV加入S
    	visited[beginV] = 1 ;
    	for(int i=0;i<numV;i++){
    		lowLR[i] = linkMatrix[beginV][i] ;
    		preV[i] = beginV ;
    	}
    	lowLR[beginV] = 0 ;
    	preV[beginV] = -1 ;  //树根的标记
    	int selectV = beginV ;
    	for(int i=1;i<numV;i++){
    		for(int j=0;j<numV;j++){
    			newCost = lowLR[selectV]+linkMatrix[selectV][j] ;
    			if(visited[j]==0&&newCost<lowLR[j]){
    				lowLR[j] = newCost ;
    				preV[j] = selectV ;
    			}
    		}
    		min = INF ;
    		for(int j=0;j<numVlj++){
    			if(visited[j]==0&&lowLR[j]<min){
    				min = lowLR[j] ;
    				selectV = j ;
    			}
    		}
    		visited[selectV] = 1 ;  //更新被选中顶点的状态
    	}
    }
    

    最小生成树MST

    在这里插入图片描述
    最小生成树性质

    • 生成树有V个顶点,V-1条边
    • 生成树中增加一条边则会得到一个回路,回路中删除任何一条边又得到一棵树
    • 设G=(V,E)是连通带权图,U是V的真子集。如果(u,v)属于E,其中u属于U,v属于(V-U),称之为跨边,且在所有这样的边中,(u,v)的权C(u,v)最小,那么一定存在G的一棵最小生成树,它包含边(u,v).
      两种求解算法
      Prim算法(加点法):针对图中的顶点设计贪心策略,逐步添加点/边构造最小生成树
      策略是选择最小跨边。
      在这里插入图片描述
      代码:
    #define MaxV 1000
    #define INF 0x3f3f3f3f  //预定义充分大的值
    int prim(int linkMatrix[][MaxV],int numV){
    	int visited[MaxV] = {0} ;   //节点是否加入MIS的标记表,0表示未加入,1表示已加入
    	int lowCost[MaxV],closet[MaxV] ;
    	int i,k ;
    	int min,costMST = 0 ;
    	visited[0] = 1 ;  //顶点加入MST
    	closetst[0] = -1 ;  //树根的标记
    	for(int i=1;i<numV;i++){   //初始化
    		lowCost[i] = linkMatrix[0][i] ;
    		closest[i] = 0 ;
    	} 
     	for(int i=0;i<numV;i++){
    		min = INF ;
    		int selectV = 0 ;
    		for(int k=1;k<numV;k++){    //贪心选择最短边
    			if(!visited[k]&&lowCost[k]<min){
    				min = lowCost[k] ;
    				selectV = k ;
    			}
    		}
    		costMST += min ;   //更新MST树权重
    		visited[selectV] = 1 ;
    		for(k=1;k<numV;k++){
    			if(!visited[k]&&linkMatrix[selectV][k]<lowCost[k]){
    				lowCost[k] = linkMatrix[selectV][k] ;
    				closest[k] = selectV ;
    			}
    		}
    	}
    	return costMST ;
    }
    //O(|V|^2)
    

    Kruskal算法(加边法):针对图中的边设计贪心策略,逐步合并分支构造最小生成树,策略是选择最短边合并两个不连通分支。
    这里先补充一下并查集的概念:并查集是一种树形的数据结构,常用于处理一些不想交集合的合并和查询问题,它包含两个基本操作:查询Find和合并Union.(每个集合找一个代表),下面部分是讲解并查集的优化方法(采用了路径压缩),更详细的解释:https://blog.csdn.net/weixin_44508223/article/details/102648509
    第一步Find:路径上的每个节点都直接连接在根上。递归的访问当前节点到树根的路径,改变每一个节点的引用到根节点。

    //初始化father[]数组为-1,也就是,代表树中只有一个节点
    int Find(int x){
    	int p = x ;
    	while(father[p]>0)
    		p = father[p] ;   //找到树根
    	return p ;
    	//将每一个节点都指向根节点
    	while(father[x]!=p&&father[x]>0){
    		int temp = father[x] ;
    		father[x] = p ;  //指向树根
    		x = temp ;
    	}
    	return p ;
    }
    

    第二步Union:按秩合并,即总是将更浅的树连接至更深的树上,避免增加合并数的秩。(这里的秩表示树的深度,单个元素的树的秩定义为0),当两个树的秩同为r时,它们的秩变为r+1,为了方便比较,把集合的秩的相反数存储在根节点。

    void Union(int x,int y){
    	int xRoot = Find(x) ;
    	int yRoot = Find(y) ;
    	if(xRoot==yRoot)  return ;
    	if(-father[xRoot]>-father[yRoot])
    		father[yRoot] = xRoot ;
    	else{
    		if(father[xRoot] == father[yRoot])
    			father[yRoot] -= 1 ;   //相等
    		father[xRoot] = yRoot ;
    	}
    }
    

    Kruskal算法俗称闭环法,该算法的实现关键是在加边时避免出现环路,用并查集来实现连通分支查找和合并的相关操作。
    一开始各个顶点是孤立的,然后选择边集中权值最小的边(i,j),如果加入不产生回路,则加入,否则舍弃,直到加够n-1条边为止。
    在这里插入图片描述

    int Kruskal(node juSet[MaxV],int numV,edge degeSet[MaxE],int numE){
    	qsort(edgeSet,numE,sizeof(struct edge),cmp) ;   //将边排序
    	int totalCost = 0,cntE = 0,fatherX,fatherY ;
    	for(int i=0;i<numE;i++){
    		fatherX = Find_Set(edgeSet[i].x) ;
    		fatherY = Find_Set(edgeSet[i].y) ;
    		if(fatherX!=fatherY){
    			Union(fatherX,fatherY) ;
    			totalCost += edgeSet[i].w ;
    			cntE++ ;
    		}
    		if(cntE == numV-1) // 完成
    			return totalCost ;
    	}
    }
    //O(elog(e))
    
    展开全文
  • 自己写的哈夫曼树的构造和求最短路径,typedef struct { int weight; int parent; int lchild; int rchild; }HNodeType; int n;HNodeType HuffNode [MAXNODE]; void HaffmanTree(HNodeType HuffNode [ ])
  • 中的内容: --------------------------------------------------------------------------------------------------------------------------------- 图中的内容: ...带权图的最短路径和距离:

    树中的内容:

    ---------------------------------------------------------------------------------------------------------------------------------

    图中的内容:

     带权图的最短路径和距离:

    展开全文
  • 哈夫曼树=带权路径长度最短的树(要么都比二叉树或者三叉树) 1.哈夫曼树权值越大的叶子越靠近根 2.具有相同带权节点的哈夫曼树不为一 步骤 1.构造森林全是根 2.选俩个小的为左右子树,根为权之和 3.将这棵树放进...
  • (1)设需要编码的字符集为{d1, d2, …, dn},它们出现的频率为{w1, w2, …, wn},应用哈夫曼树构造最短的不等长编码方案。 提示: 哈夫曼树(Huffman Tree),又叫最优二叉树,指的是对于一组具有确定权值的叶子结点的...
  • 题目1172:哈夫曼树 时间限制:1 秒 内存限制:32 兆 特殊判题:否 题目描述: 哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即...
  • JAVA数据结构算法JAVA广度优先搜索JAVA平衡二叉数B树JAVA哈夫曼树JAVA最短路径JAVA堆排序JAVA冒泡排序
  • 1172 哈夫曼树 最小路径长度

    千次阅读 2014-03-01 18:00:32
    需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入:  输入有多组数据。  每组第一行输入一个数n,接着输入n个叶节点(叶节点...
  • 正常想要计算哈夫曼树路径长度之和,是遍历一遍树,将叶结点的权值乘上深度再加和。 那么对于路径和的计算有这样一个公式: 哈夫曼树的带权路径长度和=等于所有非叶节点的权值和 所以说我们只需要每次将数组前两个...
  • 构造哈夫曼树(贪心算法) 权值越大的叶子离根越近 构造森林全是根(每个结点都做根,造成结点个数的森林) 选用两小造新树(选出两个权值小的树作为左右子树构造一个新的树) 删除两小填新人(新树的权值是...
  • 四种算法概述: http://www.cnblogs.com/aiyelinglong/archive/2012/03/26/2418707.html 最小生成 prime算法和Kruskal算法详解: http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
  • 哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 二.实现步骤: 1.构造一棵哈夫曼树 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符 三.设计思想: 1.首先要构造一棵...
  • 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出哈夫曼树的带权路径长度(WPL)。 输入格式: 第一行输入一个数n,第二行输入n个叶结点(叶结点权值不超过1000,2<=n&...
  • 哈夫曼树的构建与最小带权路径长度

    千次阅读 多人点赞 2020-06-02 14:19:57
    给定n个数值{ W1,W2,…,Wn},若将它们作为n个结点的权,并以这n个结点为叶子结点构造一颗二叉树,那么就可以构造出多棵具有不同形态的二叉树,其中带权路径长度最短的那棵二叉树称为哈夫曼树,或
  • 贪心思想和案例(活动安排问题,0-1背包问题,最优装载,哈夫曼编码,单源最短路径,最小生成(Prim,Kruskal),汽车加油问题)。算法课使用的ppt,可结合我的博客算法专栏一起看。有详细代码。
  • 【数据结构与算法基础】最短路径问题

    千次阅读 多人点赞 2020-11-25 09:40:33
    这使得我们不禁想到刚刚讨论的dijkstra算法可以出单源最短路径,如果对每个点都使用一遍这个算法,是不是就能够得出任意两点间的最短路径了呢? 答案是肯定的,对每个点都跑一遍dijkstra确实可以得到任意两点间的...
  • 头歌数据结构构建哈夫曼树及编码 第1关构建哈夫曼树 ...第一关:根据字符个数及字符出现的频率,构造带权路径最短的最优二叉树(哈夫曼树); 第二关:根据构建好的哈夫曼树构造字符的前缀编码(哈夫曼编码)。
  • 数据结构之哈夫曼树

    千次阅读 2020-12-18 19:46:34
    2.哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 问题分析 那么这时就有新的问题出现!需要我们解决了 1.什么是路径呢?路径长度是什么? 2.什么是权和带权路径长度是什么? 3.带权路径长度最短的树...
  • 2016复旦大学计算机复试上机第三题...思路2:(简单方法):你会发现就是求哈夫曼树的非根结点权值之和,或者所有非叶结点之和等于所长度。 思路二实现方法: priority_queue 优先队列: priority_queueq; 默...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,158
精华内容 3,263
关键字:

哈夫曼树求最短路径