精华内容
下载资源
问答
  • 哈夫曼树和哈夫曼编码1.将权值从小到大排序;2.然后每次选取最小的两个节点,组成新的节点(原来两个节点的 和)放入有序序列;3.接着选择最小的两个。哈夫曼树的左分支为0,右分支为1,从根节点到每个节点比如经历...

    哈夫曼树和哈夫曼编码

    1.将权值从小到大排序;2.然后每次选取最小的两个节点,组成新的节点(原来两个节点的 和)放入有序序列;3.接着选择最小的两个。

    哈夫曼树的左分支为0,右分支为1,从根节点到每个节点比如经历两次右分支则,编码就是11.

    二叉排序树

    选取第一个为根节点,然后把下一个要插入的节点与根节点进行比较,大的放在右子树,小的放在左子树位置。

    最小生成树

    不管是哪种最小生成树的方法,权值之和都是唯一的。

    克鲁斯卡尔:把所有的权值按照从小到大排列,然后去掉所有的边,按照从小到大连接,然后删除形成环的边。

    prim普里姆算法:写出邻接矩阵,此部分转自https://blog.csdn.net/weinierbian/article/details/8059129/


    ———————>先写出其邻接矩阵

    第一步:从①开始,①进集合,用与集合外所有顶点能构成的边中找最小权值的一条边
    ①——②权6
    ①——③权1 -> 取①——③边
    ①——④权5

     

    第二步:③进集合,①,③与②,④,⑤,⑥构成的最小边为
    ①——④权5
    ③——⑥权4 -> 取③——⑥边

    第三步:⑥进集合,①,③,⑥与②,④,⑤构成的各最小边
    ①——②权6
    ③——②权5
    ⑥——④权2 -> 取⑥——④边

    第四步:④进集合,①,③,⑥,④与②,⑤构成的各最小边
    ①——②权6
    ③——②权5 -> 取③——②边
    ⑥——⑤权6

    第四步:②进集合,①,③,⑥,②,④与⑤构成的各最小边
    ②——⑤权3 -> 取②——⑤边


    展开全文
  • 什么是贪心算法 顾名思义,贪心算法是通过判断当前状态下看起来最好的结果,作为最好的结果。...还真不一定,我们需要进行证明,证明的关键点是优化子结构贪心选择性。 优化子结构在dp问题中也是谈了很多次了,也

    什么是贪心算法

    顾名思义,贪心算法是通过判断当前状态下看起来最好的结果,作为最好的结果。
    一般来说,我们使用贪心算法的情况为需要一步步解决的问题,其中的每一个步骤都有一系列的选择,
    比如01背包问题,我们有C容量的背包,上来就选择能装下的最大价值物品,然后对剩下容量继续上述操作。
    (当然,如果知道的话,这种做法是错误的,我们将在后序给出讲解)

    所以问题就来了,我们通过贪心算法一定能得到最优解吗?
    还真不一定,我们需要进行证明,证明的关键点是优化子结构贪心选择性

    优化子结构在dp问题中也是谈了很多次了,也就是整体最优是否能保证局部最优的问题,
    这里我们要证明整体的最优解减去贪心的选择后剩下的部分仍为子问题的最优解。
    (因为有子结构的存在,所以我们每一次的选择其实都可以通过第一步的证明类比出来。)

    贪心选择性则需要强调一下,主要的落点还是选择,即我们选择的解是否一定在整体的最优解里面。

    其实通过上面的例子和我们的分析,大约就能猜到dp和贪心之间有着千丝万缕的关系:

    • 首先吧,他们解决的问题都是存在子结构的,而且都需要保证子结构最优
    • dp说白了就是通过一个个的尝试,在最后给出一个最优解,
      而我们的贪心算法则是通过证明来给出一个选择方式,直接判断出哪一个选择是最优的,不需要比较,
      所以贪心是要比dp快很多的,但是需要一个证明。
    • 似乎看起来贪心能使用的情况下,dp都是成立的,其实很多问题确实如此,毕竟一次次比较也很难得不到最优解,但是对于最小生成树算法,比如prim和kruskal算法,这两个都是贪心算法,而dp的算法却很难给出。

    任务安排问题

    纸上谈兵终究很难抓住重点,我们先举一个例子,就是经典的任务安排问题。

    定义

    有一系列的任务,每一个任务都有开始和结束的时间,我们需要选择尽可能多但是不可以重叠的问题集。

    既然是贪心算法,我们就需要有一个选择最优的判准,下面先给出几个

    1. 按照任务开始的时间,越早开始越好
    2. 按照任务结束的时间,越早结束越好
    3. 按照任务的时间长度,越短的越先开始。

    这里我们直接给出答案,最早结束(或者最晚开始的活动也行)这一选择方式是可以证明的。

    证明

    贪心最重要的就是证明了,接下来我们看看应该怎么进行。

    首先是优化子结构,我们还是采用反证法的方式。
    我们贪心的选择是最早结束的活动a,最优解为S,那么X = S-a也一定为最优解。
    (子结构为整体减去活动a)
    如果不是最优解,那么我们就能找到另外一个X’,他比S‘的活动更多,当我们加上活动a时,很明显有:
    X’+a > S’+a = S,而和S是最优解矛盾,所以子结构X一定最优,故得证。

    然后是贪心选择性,也就是我的选择一定是在整体的最优解里面。
    我们假设最优解为S,整个活动的最早结束活动为a,S中最早结束的活动为b
    如果a == b,得证;
    如果不等,因为a结束比b早,所以a和S-b一定没有交集,此时我们将b去掉,然后加上a,得到的S‘和S任务数相同,也为一个最优解,所以我们选择的a一定在一个最优解里面,得证。
    (如果是最晚开始的活动也同理,这里不做证明)

    在证明之后,我们就可以直接使用了,那就没什么可以讲的了。

    哈夫曼树

    之前也发过哈夫曼树的博客,但是没有讲到贪心的思想,这次补一下。

    最开始没有接触贪心的时候只是感觉哈夫曼树属于一种很有意思的算法,这次受教了。

    在这里我们就不再提定义了,直接看贪心的部分,这里的贪心是将两个最小的结点取出来,合并为一个大的结点(这里的大小指的是概率),这样能保证我们得到的编码树代价最小。

    优化子结构

    我们假设一棵树T是集合G最优的,其中我们贪心的选择是最小的两个结点m、n。
    在去掉nm的树T‘中,nm的父节点x作为了新的叶子节点,其值为x = m+n。
    如果T’不是G-m-n+x的最优解,那么我们可以找到更优解T‘’,当我们将T’‘加上m、n两个结点,一定是比T的代价还小,和题目不符,所以得证。

    (多了一层,就相当于加了一份m+n的代价,对两棵G’构成的树是一样的,还是看剩余部分的代价)

    贪心选择性

    我们需要证明我们每一次选择的两个最小值一定是在最优解中的。
    假设两个最小值为x、y,那么一定存在一棵最优哈夫曼树,其中xy为最后一层的两个相邻叶子结点(编码长度相同,只有最后一位不同。

    取一棵最优哈夫曼树中最大深度的两个相邻叶子节点mn,然后我们交换x与n、y与m,那么我们得到了一棵新的哈夫曼树,因为我们将概率更小的元素放在了下层,而代价一定不比之前大(因为可能相同),所以我们得到了一棵最优哈夫曼树,得证。

    实现

    我们可以使用最小堆来实现,之前关于堆的博客,每一次弹出最小的两个元素,然后构造即可。

    最小生成树问题

    定义

    在一个无向加权图中找出一棵生成树,保证生成树的边长和最小。
    比如下面的图,我们需要的就是红色的边,其边之和最小。
    在这里插入图片描述
    生成树的性质:

    • 生成树一定是包含了图的所有顶点,且没有形成环
    • 生成树的边数为顶点数减一,属于树的性质
    • 最小生成树中任意添加一条边,一定会形成一个环。(图论内容)

    接下来我们看一下生成树的一个算法

    kruskal

    思想:
    将所有的边排序,然后从最小的边开始,如果该边的两个顶点不属于一个,那么就划为一个(Union操作),直到所有的顶点都属于一个集合。(其实是边遍历结束,因为每一次都检测代价太大)
    个人感觉其实谈不上合并,只需要最开始每一个顶点给一个编号,需要合并的时候修改一下编号就行了。
    伪代码:

    MST-Kruskal(G,W)
    A=Φ;
    For V v∈V[G]
    	Make-Set(v);
    sort(E[G]);//对边进行排序
    For (u, v)∈E[G] (按W值的递增顺序)
    	If Find-Set(u) != Find-Set(v)
    		A=AU{(u, v)};  
           	Union(u, v);
     Return  A
    

    其中V为任取,U为求并操作。

    整体的代价就属排序最大,我们取O(mlogm),m为边数

    证明

    贪心选择性

    因为我们每一次选择的是最小边,所以我们需要证明最小边一定在整个的最小生成树中。
    我们假设有最小生成树T,其中没有最小边uv,此时我们将最小边加进去,一定会形成一个环,然后我们将其中的一条边删掉(这条边可以是顶点u或者v的另外一条边),就可以再次构成一棵树,此时的树代价是要比之前的小的,所以最小生成树中一定有uv。

    优化子结构

    先给一个操作,我们定义“-”表示将两个顶点合并成一个顶点的操作
    首先假设T为最优的生成树,我们已经知道了T一定含有uv,那么设T’ = T-uv是G-uv的最小生成树。
    (将最小生成树T中uv顶点合并,G中uv顶点合并,我们叫这个新结点为a)
    如果不是,那么我们就能找到T’’,因为是G-uv的生成树,所以一定包含了a这个顶点,当我们将分隔为原来的u和v时,我们再将uv边加上,发现T’’+uv的生成树代价是要比T小的,和定义不符,得证。

    prim

    思想:每一次从当前已经遍历的顶点构成的集合(刚开始集合为空)中找连接出去的边的最小值。
    比如这张图中我们已经遍历了AE,这个集合连接出去的边有ab、ad、be、de这些,我们取其中最小的ad,同时将取到的顶点划入集合中,直到集合为全集。
    在这里插入图片描述
    伪代码:

    MST-Prim(G,W,r)//输入连通图G,权值函数W,树根r 输出G的一棵以r为根的生成树
    C={r};									//顶点集		
    T=Φ;									//最小生成树的构成
    建堆Q维护C与V-C之间的边
    While C != V
    	uv=Extract_Min(Q)					//横跨C和V-C
    	C = CU{v};      					//顶点划入顶点集
    	T = TU{uv}; 						//最小生成树的一条边
    	for x∈Adj[v]						//新加入的顶点v的相邻边需要处理
    		if x∈C 						//相邻边的两端都在C中,直接删了就行
    			将vx从Q中删除
    		Else							//如果是新的边,那就是连接C和V-C的边,需要加入Q中
    			将vx插入Q
    Return  T
    

    解释一下:

    • V为总顶点集,而我们创建的顶点集为C,剩下的就是V-C了
    • Q为存储C和V-C之间的边的堆,其中我们取出的边uv,u在C中而v不在

    证明

    贪心选择性

    我们每一次选择的是点集和点集之外的点构成的最短边uv,我们假设一棵最小生成树T不含有边uv,
    当我们在T中添加uv,那么一定会形成环,此时我们将u的另外一条边断开(这条边也是属于连接的边,且一定是要比uv长的),我们新得到的生成树是要比之前的树还小,说明一定含有uv,得证。

    优化子结构

    我们每一次选择的是C中的顶点u和V-C中的顶点v之间的边(假设已经确定这条边最小)
    最开始的时候,C为只有一个元素,所以uv也就是这个点的最小边。
    我们还是采用T-uv和G-uv的方式来,和上面的基本相同,就不证了。

    一些不能用贪心的例子

    首先就是最开始提到的01背包问题,我们在选择了价值最大的物品之后不能证明符合贪心选择性。
    但是如果问题改成存在0.1这样的选项,而非一定要都拿走或者不拿,那么贪心就可以解决问题。
    (这个有一个叫法叫做拿金砖还是拿金砂的问题)

    然后就是硬币找零问题,感觉这两个其实是很相近的问题,在dp中,01背包是有一个吐出来的过程,但是贪心是选好了就不能反悔,但我们不能保证选的一定是最好的。
    这应该就是不能的主要原因了吧。

    补充一个贪心小问题

    这个应该是leecode上的问题:

    题目描述:老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子
    的表现,预先给他们评分。
    你需要按照以下要求,帮助老师给这些孩子分发糖果:
    每个孩子至少分配到 1 个糖果。
    相邻的孩子中,评分高的孩子必须获得更多的糖果。
    那么这样下来,老师至少需要准备多少颗糖果呢?
    示例 1:
    输入: [1,0,2]
    输出: 5
    解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
    示例 2:
    输入: [1,2,2]
    输出: 4
    解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
    第三个孩子只得到 1 颗糖果,这已满足上述两个条件。

    这里我们的解决思路:
    先每一个人发一颗糖。
    因为两边都要看,我们就先看一边,从左到右,
    如果后面的孩子比前面的高,那么就让后面的孩子糖果数为前面的孩子+1,否则不变;
    然后从右到左重复一遍,也是后面的和前面的比较。
    当两次遍历结束,我们得到了两组数据,对比两个数组,每一个位置取其中的较大值,最终得到的数组就是答案了。

    这个问题说实话,证明起来不太好证,不过确实比较直观,很有贪心内味。

    展开全文
  • 最小生成树哈夫曼树

    千次阅读 2019-08-25 10:41:44
    定义:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。 算法: Kruskal算法(加边法):初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。 ...

    转载自添加链接描述

    最小生成树

    定义:在连通网的所有生成树中,所有边的代价和最小的生成树,称为最小生成树。
    算法:

    1. Kruskal算法(加边法):初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。
    2. Prim算法(加点法):每次迭代选择代价最小的边对应的点,加入到最小生成树中。算法从某一个顶点s开始,逐渐长大覆盖整个连通网的所有顶点。

    哈夫曼树

    定义:哈夫曼树又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中,带权路径长度 WPL 最小的二叉树。
    算法:在森林中选出两个根结点的权值最小的树合并,加入到森林,并把原来的两个树删除,重复此过程直至森林中只有一棵树为止。

    展开全文
  • C/C++实现哈夫曼树和生成哈夫曼编码

    千次阅读 2019-07-01 14:52:39
    用C语言实现哈夫曼树和生成哈夫曼编码,首先生成哈夫曼树,哈夫曼树是从中选取权值最小的两个进行相加,将这两个分别做为生成的左子树和右子树,左子树要比右子树小。然后将相加得到的值从新放入,然后又从中找到...

    用C语言实现哈夫曼树和生成哈夫曼编码,首先生成哈夫曼树,哈夫曼树是从中选取权值最小的两个进行相加,将这两个分别做为生成的左子树和右子树,左子树要比右子树小。然后将相加得到的值从新放入,然后又从中找到最小的两个值,然后用这个两个值一直相加,直到只剩最后一个值,将这个值作为哈夫曼树的根。
    生成哈夫曼编码,如果是左子树的话为0,右子树的话为1,从父节点还是往下找。然后这串代码就是哈夫曼编码。

    上代码

    
    
    
     #include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    #include<bits/stdc++.h>
    
    
    using namespace std;
    
    
    const int Lsize  = 1000000;
    
    typedef struct{
    
       int order;//序号
       char character;//字符值
       int weight;//权重
       int parent;
       int lift_Child;
       int right_Child;
       int deep;
       int code[100];//哈夫曼编码
    }Nodetree,*HuffmanTree;
    
    
    typedef struct node{
    
       char symbol;
       int quantity;
       struct node *next;
    }Node;
    
    
    
    
    int getListSize(char *pStr){
    
        int len=0;
        char *start = pStr;
        while(*start){
            len++;
            start++;
        }
        return len;
    }
    
    int getLIstLink(Node *head){
    
       int a = 0;
       Node *p = head->next;
       while(p){
         a++;
         p = p->next;
       }
       return a;
    };
    
    //打印链表
    void print(struct node *head){
    
        struct node *p ;
        printf("开始打印\n");
        p=head->next ;
        if(p == NULL){
            printf("值为空\n");
        }
        while(p!=NULL){
         printf("          %c",p->symbol);
         printf("         %d\n",p->quantity);
         p=p->next;
        }
    };
    
    
    
    int QueryNOde(Node *head,char ch){
    
        Node *p;
        p = head->next;
        while(p!=NULL){
            if(p->symbol == ch){
                p->quantity = p->quantity + 1;//字符存在节点加1
                return 1;//这个字符已经存在
            }
            p = p->next;
        }
       return 0;//这个字符不存在
    };
    
    //生成权值
    Node *createWeight(char *str){
    
        Node *head , *q ,*p;
        int list_size = getListSize(str);
        q=head=(struct node*)malloc(sizeof(struct node));
         for(int i = 0 ; i < list_size ; i++){
                //printf("当前的值:%c\n",*str);
                if(QueryNOde(head,*str)==1){//如果该数据已经存在,则节点加1
                      //  printf("开始遍历\n");
                    // Node *boos = head = (struct node*)malloc(sizeof(struct node));
                       // printf("开始查找\n");
                    // while(boos){
                      //  printf("进入查找\n");
                       // printf("当前遍历值为:%c\n",boos->symbol);
                       // if(boos->symbol == *str){
                          //  printf("开始修改值\n");
                           // boos->quantity = boos->quantity + 1;
                           // printf("值相同\n");
                           // break;
                       // }
                       // boos = boos->next;
                     //}
                    } else{//生成新的权值
                        p = (struct node*)malloc(sizeof(struct node));
                        p->quantity = 1;
                        p->symbol = *str;
                        p->next = NULL;
                        q->next = p;
                        q = p;
                        //printf("值不同\n");
                    }
                     str++;
                }
                return head;
    };
    
    
    void createTree(HuffmanTree &root,int n,Node *head){
    
        if(n<=0){
            return;
        }
        Node *q;
        q = head->next;
        int length = 2*n - 1;
        printf("n is %d\n",n);
        int HFCode[100];//哈夫曼编码数组
        root = new Nodetree[length+1];
        //初始化哈夫曼树
        for(int i = 1;i<=length;i++){
            root[i].order = i;
            root[i].character = 0;
            root[i].parent = 0;
            root[i].lift_Child = 0;
            root[i].right_Child = 0;
        }
        //给哈夫曼树赋值
        for(int i = 1;i<=n;i++){
            root[i].character = q->symbol;
            root[i].weight = q->quantity;
            q = q->next;
        }
    
    
        //开始建立哈夫曼树
    
          for(int i = n+1; i <=length; i++){  //进行 n-1 次循环建立哈夫曼树
            //k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标
            int k1 = -1 , k2;
            for(int j = 0; j < i; j++){
                if ( root[j].parent == 0  && k1 == -1 && root[j].weight > 0){
                    k1 = j;
                    continue;
                }
                if (root[j].parent == 0 && root[j].weight > 0){
                    k2 = j;
                    break;
                }
            }
            //将指针数组中的指针指向的最小值赋值给索引号为k1的,次小值赋值给索引号为k2的
            for (int j = k2; j < i; j++){
                if(root[j].parent == 0 ){
                    if(root[j].weight < root[k1].weight){
                        k2 = k1;
                        k1 = j;
                    }else if(root[j].weight < root[k2].weight){
                        k2 = j;
                    }
                }
            }
            //开始生成新的哈夫曼树节点
            root[k1].parent = i;
            root[k2].parent = i;
           // printf(" i is:%d\n",i);
           // printf("k1 is :%d\n",k1);
           // printf("k2 is :%d\n",k2);
           // printf(" k1 weight is:%d\n",root[k1].weight);
           // printf(" k2 weight is:%d\n",root[k2].weight);
            root[i].order = i;
            root[i].lift_Child = k1;
            root[i].right_Child = k2;
            root[i].weight = root[k1].weight + root[k2].weight;
          }
              int start;
             // HFCode[n-1]='\0';
             //生成哈夫曼编码
          for(int i = 1;i<=n;i++){
              start = 0;
              int deep = 0;//节点的深度
              int c = i;
              int f = root[i].parent;
              while(f!=0){
                //printf("tart is:%d\n",start);
                if(root[f].lift_Child == c){
                    root[i].code[start] = 0;//如果为左子树就为0
                }else{
                   root[i].code[start] = 1;//右子树就为1
                }
                deep++;
                start++;
                c = f;
                f = root[f].parent;
              }
              root[i].deep = deep;
             // printf("code is:%d\n",root[i].code[start]);
          }
    
    };
    
    
    
    //void CreatHFCode(Nodetree *root,)
    //打印哈夫曼树的表态结构
    void printTree(Nodetree *root,int n){
    
       int length = 2*n -1;
       for(int i = 1 ;i<=length;i++){
        printf("order is %d   character is %c"   "  parent is %d  LiftC is %d  rightC is %d   weight is %d  deep is %d   ",root[i].order, root[i].character, root[i].parent,root[i].lift_Child,root[i].right_Child, root[i].weight,root[i].deep);
           int deep = root[i].deep;
             printf("HFCode is  :");
            for(int j=deep-1;j>=0;j--){
                printf("%d",root[i].code[j]);
            }
            printf("\n");
       }
    
    };
    
     void QueryCOde(Nodetree *root,int n){
    
         int query_list[100];//哈夫曼编码整数数组
         int flag ;//哈夫曼编码匹配判断标志
         int c;
         int code_Size;
         char query_char[100];//用来接收哈夫曼编码
         scanf("%s",&query_char);
         //printf("%s\n",query_char);
         code_Size = getListSize(query_char);//输入的哈夫曼编码长度
    
         //将输入的哈夫曼编码有字符数组转换为整数数组
         for(int i = 0;i<code_Size;i++){
            c = query_char[i]-'0';
            query_list[i] = c;
           // printf("n is:%d\n",c);
         }
    
       // for(int i=0;i<code_Size;i++){
           //  printf("%d ",query_list[i]);
        // }
    
         for(int i=1;i<=n;i++){
            int deep = root[i].deep;
            int j ;
            //若哈夫曼的深度和输入的哈夫曼编码长度相同则开始查找
            if(deep==code_Size){
                //printf("deep is:%d code_size is:%d\n",deep,code_Size);
                 j=0;
                 int code = code_Size-1;
                deep--;
                //开始匹配值
                flag = i;
                while(deep>=0){
               // printf("开始匹配deep %d\n",deep);
                if(root[i].code[j]!=query_list[code]){
                   //printf("值不相同\n");
                   flag = -1;
                   break;
                }
                j++;
                code--;
                //printf("%d deep is %d\n",i,deep);
                deep--;
            }
            }
            //判断是否找到对应的权重的值
           // printf("deep is:%d\n",deep);
            if(deep<0){
                flag = i;
                i = n+1;
            }
    
         }
        // printf("flag is:%d\n",flag);
         if(flag>0){
            printf("翻译结果值:%c\n",root[flag].character);
         }
         else{
            printf("没有与编码匹配的数据值\n");
         }
    
     };
    
    
    
    int main()
    {
        int Link_size ;
        struct node *head;
        Nodetree *root;
        char input_list[Lsize];
    
    
    
         printf("........................功能列表...................\n");
         printf("..............         输入报文  ................\n");
         printf("..............         打印频度  ................\n");
         printf("..............         建立哈夫曼树  ................\n");
         printf("..............         翻译报文  ................\n");
         //printf("..............         5.退出  ................\n");
    
    
    
    
    
        printf("..............输入想要赋值的字符串\n");
        scanf("%s",&input_list);
        gets(input_list);
        printf("%s\n",input_list);
        head = createWeight(input_list);
        printf("..............出现频度为\n");
        print(head);
        Link_size = getLIstLink(head);
        printf("..............链表长度为:%d\n",Link_size);
        createTree(root,Link_size,head);
        printTree(root,Link_size);
    
        int flag = 1;
        while(flag==1){
            printf("..............输入你想要查找的代码\n");
            QueryCOde(root,Link_size);
            printf("..............想继续查找输入1,不想输入0\n");
            scanf("%d",&flag);
        }
    
    }
    

    代码里面有备注,不清楚的可以留言,有错误的欢迎指出。

    展开全文
  • 哈夫曼树 计算最小WPL

    2020-03-14 16:25:57
    需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之。 输入描述: 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点...
  • 实验要求 实验目的 1 掌握二叉树基本操作的实现方法 2 掌握二叉树基本操作的实现方法 3 了解哈夫曼树的思想相关概念 4 学习使用二叉树解决实际问题的能力 5 熟悉C++语言的基本编程方法掌握集成编译环境的调试方法...
  • 1哈夫曼树1.1哈夫曼树简介  哈夫曼树:给定N个权值作为N个叶子节点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树...
  • 1172 哈夫曼树最小路径长度

    千次阅读 2014-03-01 18:00:32
    需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之。 输入:  输入有多组数据。  每组第一行输入一个数n,接着输入n个叶节点(叶节点...
  • 你并比任何人聪明! 你所拥有的只是,吸取别人的优点,发现自己的问题,谦卑自己的学习态度,不断学习 你只有不断学习,才能不落后!...哈夫曼树 和最小生成树一样吗??? 它们的区别是什么???
  • 问题 C: 哈夫曼树 ...需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之。 输入 输入有多组数据。 每组第一行输入一个数n,接着输...
  • 每次选择权最小的两个树将他们的根结点合并,生成新的树,放入原理的森林中, 重复上述操作,直到只有一个树,此时即得到哈夫曼树 #include #include #include #include #include #include using namespace std; ...
  • 生成哈夫曼树

    2020-01-05 20:43:23
    哈夫曼树的模板题,每次去两个最小的数,相加,再把它们的加入数组。 #include<iostream> #include<string> #include<cstring> #include<cmath> #include<cstdio> #include<qu...
  • 哈夫曼树:具有最小带权路径长度的二叉树: 图的深度遍历广度遍历简单理解: 一个节点一个节点,一层一层的, 图的最小生成树: 普里姆算法: 克鲁斯卡尔算法:
  • 哈夫曼树

    2021-02-10 10:20:58
    需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之的最小值。 输入描述: 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点...
  • 二叉树带权路径长度:设二叉树有n个带有权值的叶子结点,每个叶子到根的路径长度乘以其...哈夫曼树的构造过程假定有n个具有权值的结点,则哈夫曼树的构造算法如下: ① 根据n个权值,构造n棵二叉树,其中每棵二叉树...
  • 哈夫曼树要求所有(叶子节点)权值*深度的最短。 为了说明方便,设节点的值与权值相等。 哈夫曼树的构建 通过观察可以看出,权值小的在下,大的在上。由此可以很容易理解构建的规则: 将所有的节点(或者说是只有...
  • 构建哈夫曼树成功,其内容已保存在hfmTree.txt文件中!!!"<<endl;  system("pause"); } <p><br /> //输入字符,用于实现哈夫曼编码 void Encoding...
  • 在 F 中选取其根结点的权值为最小的两棵二叉树分别作为左右子树构造一棵新的二叉树并置这棵新的二叉树根结点的权值为其左右子树根结点的权值之; 3.从F中删去这两棵同时将刚生成的新加入到F中;例如: 已知权值 W...
  • 哈夫曼树实现

    2020-03-12 12:00:51
    2、利用优先队列,每次从森林中pop出两个权重最小的节点,生成新的节点,新节点的权重是它们俩的权重,把新节点加入到森林里面(优先队列中); 3、重复以上过程n-1次,直到最后队列中只剩下一个节点; 结点结构:...
  • 1.哈夫曼树的构造 给定N个权值为{w1,w2,w3,…,wN}的结点(比如可以根据一个字符串中字母出现的频率计算权值)。构造哈夫曼树的算法流程如下: 1.将这N个结点分别作为N棵仅含一个结点的二叉树,构成森林F; 2.构造一...
  • 哈夫曼编码译码 基本要求:  输入为:一段英文或中文的文章(原文)  对输入的文章构造哈夫曼树生成对应的编码 ...首先先构造一棵哈夫曼树,在构造哈夫曼树的算法中,需要选择根权值最小和次小的树
  • 运用堆实现哈夫曼树

    2020-07-21 11:01:52
    哈夫曼树的定义 哈夫曼树的构建 就是把两个最小的权值放左右子树上 产生父结点为他们的 再将新的父结点剩下数的比较 再找出两个最小的权值 如此循环 用最小堆可以找到两个最小的权值 并将新生成的权值加入到...
  • 需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之。 输入: 输入有多组数据。 每组第一行输入一个数n,接着输入n个叶节点(叶节点权
  • 哈夫曼树带权路径长度

    万次阅读 多人点赞 2018-08-13 16:24:51
    一. 长什么样? 左边是普通树,右边是哈夫曼树 图a: WPL=5*2+7*2+2*2+13*... 怎么生成和计算? 1. 总结 ①先对权值从小到大排序。 ②选两个最小的加起来成为一个新结点,而这两个最小的值是新结点的左右子结...
  • 哈夫曼树生成时,首先需要将2个weight最小的树叶组队,再新建一个parents给两个树叶,然后一直循环,直到构建完成。 那么,其实可以将结构体数组当成leaves节点,构建树的实际操作就是构建每个数组元素的联系,...
  • 结点的路径长度: 从根节点到该结点的路径上的连接数。 的路径长度: 中每个叶子节点的路径长度之 结点带权路径长度: ...(2)生成一个新结点,并从F中找出根结点权值最小的两棵作为它的左右子树,且新结
  • 需要用这些叶节点生成哈夫曼树。这些节点有权值,即weight,题目需要输出所有节点的值与权值的乘积之。输出权值51 2 2 5 937思路:将所有节点放入集合K,若K中剩余节点大于2,则取出最小的两个节点,构造他们同时...
  • 构造哈夫曼树:按照频率来分配的(频率递增是因为出现次数多,那么就越深权重越大),就是生成哈夫曼树,基于树形结构,然后再次插进队列里面。 频率低的,就断。频率高的就长 二、二路最佳合并 三、最小代价...
  • 相关定义 ...哈夫曼树 定义:最优二叉树,含有nnn个带权叶子结点带权路径长度最小的二叉树 构造 将nnn个结点作为nnn棵仅含有一个根结点的二叉树,构成森林FFF; 生成一个新的结点,并从FFF中找出权

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 143
精华内容 57
关键字:

哈夫曼树和最小生成树