精华内容
下载资源
问答
  • 《实战应用Java算法分析与设计(链表、二叉树、哈夫曼树、图、动态规划、HashTable算法)》 算法分析与设计Java版,是一套实用型算法课程。通过本课程的学习,学员可以掌握以下技术点:线性结构与顺序表、单向链表、...
  • 哈夫曼树构造 1.哈夫曼树的定义 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)。 2.哈夫曼树的构造 假设有n个权值,则构造...

    哈夫曼树构造

    1.哈夫曼树的定义

        给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)。

    2.哈夫曼树的构造

        假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1,w2,…,wn,则哈夫曼树的构造规则为:

    (1) 将w1,w2,…,wn看成是有n 棵树的森林(每棵树仅有一个结点);

    (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;

    (3)从森林中删除选取的两棵树,并将新树加入森林;

    (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为我们所求得的哈夫曼树。

        下面给出哈夫曼树的构造过程,假设给定的叶子结点的权分别为1,5,7,3,则构造哈夫曼树过程如图所示。 从图中可知,n 个权值构造哈夫曼树需n-1次合并,每次合并,森林中的树数目减1,最后森林中只剩下一棵树,即为我们求得的哈夫曼树。

    image

    哈夫曼构造正确性证明。

    如上图,WPL值为3×(1+3)+2×5+1×7=29.

    事实上WPL值也是所有非叶子节点的和,即4+9+16=29.

    这是可以证明的。

    从最底层开始计算,最底层的2个叶节点的根结点的值为叶节点的和,每个根结点都为叶节点的和,也就是说,每个非叶节点的值都是它底下所有的叶节点的和。比如16=1+3+5+7,9=1+3+5。因此把4,9,16这些节点加起来,就相当于底层节点1,3加了3遍,5加了2遍,7加了1遍。即每个值加的遍数就是该值的深度。

    又因为根据算法,n个叶子节点所组成的一个集合,每次取走2个最小节点,再加入一个节点,直到只剩下最后一个节点。因此,新生成的叶子非叶子节点个数必定是n-1个。因此要保证WPL值最小,也就是保证生产的非叶子节点和最小,即生成的节点和值最小。因此每次生成的节点取最小值,即可保证,总的和值是最小的。即WPL值也是最小的。















    本文转自cnn23711151CTO博客,原文链接:http://blog.51cto.com/cnn237111/1051936 ,如需转载请自行联系原作者


    展开全文
  • 构造哈夫曼树算法

    千次阅读 2016-02-02 18:43:44
    ②、构造哈夫曼树算法; ③、编写一个存放每个节点哈夫曼编码的类型; ④、编写哈夫曼树求对应的哈夫曼编码的算法; ⑤、编写主函数。 代码如下: #include #include #include #include //①: typedef ...

    ①、编写哈夫曼树中每个节点结构;

    ②、构造哈夫曼树的算法;

    ③、编写一个存放每个节点哈夫曼编码的类型;

    ④、编写哈夫曼树求对应的哈夫曼编码的算法;

    ⑤、编写主函数。

    代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<iostream>
    //①:
    typedef struct
    {	char data;		
    	float weight;
    	int parent;		
    	int lchild;		
    	int rchild;		
    } HTNode;
    //②:
    void CreateHT(HTNode ht[],int n)
    {  int i,j,k,lnode,rnode; float min1,min2;
       for (i=0;i<2*n-1;i++)	  	
          ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
       for (i=n;i<2*n-1;i++)		
       {  min1=min2=32767; lnode=rnode=-1;
    	for (k=0;k<=i-1;k++)
    	  if (ht[k].parent==-1)		
    	  {  if (ht[k].weight<min1)
    	     {  min2=min1;rnode=lnode;
    		  min1=ht[k].weight;lnode=k;  }
    	     else if (ht[k].weight<min2)
    	     {  min2=ht[k].weight;rnode=k;  }   
            } 
    	  ht[lnode].parent=i;ht[rnode].parent=i;
            ht[i].weight=ht[lnode].weight+ht[rnode].weight;
    	  ht[i].lchild=lnode;ht[i].rchild=rnode;
       }
    } 
    //③:
     typedef struct
     {  char cd[N];  
        int start;   
     } HCode;
    //④:
    void CreateHCode(HTNode ht[],HCode hcd[],int n)
    {  int i,f,c; HCode hc;
       for (i=0;i<n;i++)		
       {  hc.start=n;c=i; f=ht[i].parent;
    	while (f!=-1)   
    	{  if (ht[f].lchild==c)	
    	      hc.cd[hc.start--]='0';
    	   else	  		
    	      hc.cd[hc.start--]='1';
    	   c=f;f=ht[f].parent; 
     	 }
    	 hc.start++;		
           hcd[i]=hc;
       }
    }

          对哈夫曼树的构造可以分一下几步,需要多做几个实验,才可以熟练的掌握。

    假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:

    (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);

    (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;

    (3)从森林中删除选取的两棵树,并将新树加入森林;

    (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。


    展开全文
  • 构造哈夫曼树算法模拟。数据结构有个重要的算法。共同学习
  • 哈夫曼树构造算法

    千次阅读 2014-09-21 11:06:35
    哈夫曼树构造算法 typedef struct  {  char data;  double weight;  int parent;  int lchild;  int rchild; }HTNode; void CreateHT(HTNode ht[],int n) {  int i,j,k,lnode,rnode;  ...

    哈夫曼树的构造算法

    typedef struct 
    {
      char data;
      double weight;
      int parent;
      int lchild;
      int rchild;        
    }HTNode;

    void CreateHT(HTNode ht[],int n)
    {
      int i,j,k,lnode,rnode;
      double min1,min2;
      for(i=0;i<2*n-1;i++)
        ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
      for(i=n;i<2*n-1;i++)
      {
        min1=min2=32767;
        lnode=rnode=-1;
        for(k=0;k<=i-1;k++)
          if(ht[k].parent==-1)
          {
            if(ht[k].weight<min1)
            {
              min2=min1;
              rnode=lnode;
              min1=ht[k].weight;
              lnode=k;                     
            }
            else if(ht[k].parent<min2)
            {
              min2=ht[k].weight;
              rnode=k;     
            }                 
          }
          ht[i].weight=ht[lnode].weight+ht[rnode].weight;
          ht[i].lchild=lnode;
          ht[i].rchild=rnode;
          ht[lchild].parent=i;
          ht[rchild].parent=i;                    
      }

    展开全文
  • 哈夫曼树构造算法代码

    千次阅读 2020-05-05 21:24:19
    代码: #include<stdio.h> #define ERROR 0 #define OK 1 typedef int Status; //采用顺序存储结构,一维结构数组 //定义结点类型 typedef struct { int weight; int parent,lch,rch;...//哈夫曼树...

    代码:

    #include<stdio.h>
    #define ERROR 0
    #define OK 1
    typedef int Status;
    //采用顺序存储结构,一维结构数组
    //定义结点类型 
    typedef struct
    {
    	int weight;
    	int parent,lch,rch;
    }HTNode,*HaffmanTree;
    HaffmanTree HT;
    //哈夫曼树的构造算法 
    Status CreatHT(HaffmanTree HT,int n)
    {
    	int s1,s2;
    	if(n<=1)
    	return ERROR;
    	int m=2*n-1;//数组共2*n-1个元素 
    	int i;
    	HT=new HTNode[m+1];//构建定义好的结构体类型数组 
    	//初始化数组 
    	for(i=1;i<=m;i++) //0号下标没有用,HT[m]表示元素的根结点 
    	{
    		HT[i].lch=0;//将2n-1个元素的lch,rch,parent置为0 
    		HT[i].rch=0;
    		HT[i].parent=0;
    	}
    	for(i=1;i<=n;i++)
    	{
    		scanf("%d",&HT[i].weight);//输入前n个元素的weight值 
    	}
    	//建立哈夫曼树 
        for(i=n+1;i<=m;i++)//合并产生n-1个新结点 
    	{
    		void Select(HaffmanTree HT,int k,int &s1,int &s2);
    		//在HT[k](1<k<i-1)中选择两个双亲域为0,并且最小的结点,并返回它们在HT中的序号 
    		Select(HT,i-1,s1,s2);
    		HT[s1].parent=i;
    		HT[s2].parent=i;//表示从F中删除s1,s2 
    		HT[i].lch=s1;
    		HT[i].rch=s2;//s1,s2分别作为i的左右孩子 
    		HT[i].weight=HT[s1].weight+HT[s2].weight;//i的权值为左右孩子的权值之和	
    	}
    	return OK; 
    }
    void Select(HaffmanTree HT,int k,int &s1,int &s2)
    {
    	int i,j;
    	int min1,min2;
    	for(i=1;i<k;i++)
    	{
    		if(HT[i].parent==0)
    		{
    		    min1=HT[1].weight;
    		    s1=1;
    				if(HT[i].weight<min1)
    				{
    					int t;
    					t=min1;
    					min1=HT[i].weight;
    					HT[i].weight=t;//选出权值最小的元素 
    					s1=i;
    				}
    			min2=HT[1].weight;
    			s2=1;
    			if(HT[i].weight<min2&&HT[i].weight>min1)
    			{
    				int x;
    				x=min2;
    				min2=HT[i].weight;
    				HT[i].weight=x;//选出权值次小的元素 
    				s2=i;
    			}
    		}
    	}
    }
    //主函数测试
    int main()
    {
    	int n;
    	printf("请输入要构造成哈夫曼树的结点数:\n");
    	scanf("%d",&n);
    	printf("请输入各结点所对应的权重:\n");
    	if(CreatHT(HT,n))
    	printf("CreatHT success\n");
    	return 0;
     } 
    
    展开全文
  • 哈夫曼树算法如下 (1)根据给定的n个权值,使对应节点构成n棵二叉树的森林,其中每棵二叉树都只有一个根节点,其左右子树均为空。 (2)在森林中选取两棵节点权值最小的子树分别作为左右子树构造一棵新的二叉树,且...
  • <br />#include<stdio.h><br />#define MAX 100 #define MAXVALUE 500 typedef... /*哈夫曼树结点类型*/   /*-----------------------------以下部分定义哈夫曼编码存储结构---------------
  • 如何构造哈夫曼树,哈夫曼在 1952 年最早给出了一个带有一般规律的算法,俗称哈夫曼算法, 根据 n 个给定的权值{w1 w2 w3 …} 构成 n 棵二叉树的森林F = {T1 T2 T3…} 其中 Ti 只有一个带权为 Wi 的根结点 构造...
  • 哈夫曼树构造算法 算法思路 有W1,W2… …W1 一共n个权值的结点,把每个结点看作一棵树。 从n个结点中找出权值最小的两个结点,创建一个新结点,权值为二者的和。 两个结点分别为新结点的左右孩子(左小右大,左大...
  • (1)设需要编码的字符集为{d1, d2, …, dn},它们出现的频率为{w1, w2, …, wn},应用哈夫曼树构造最短的不等长编码方案。 提示: 哈夫曼树(Huffman Tree),又叫最优二叉树,指的是对于一组具有确定权值的叶子结点的...
  • 算法笔记》那本书上并没有直接给出哈夫曼树构造代码,特此记录一下。 核心代码: typedef struct{ char data; double weight;//权重 int parent; int lchild; int rchild; }HTNode; void Cr...
  • //构造哈夫曼树和哈夫曼编码的算法 #include &lt;stdio.h&gt; #include &lt;string.h&gt; #define N 50 //叶子结点数 #define M 2*N-1 //树中结点总数 typedef struct { char data[5]; //结点值 ...
  • 建立一棵二叉链表树,分别输出此先根、中根和后根遍历序列 将上题编程,实现哈夫曼树的构建和哈夫曼编码的设计
  • 统计下面一段英文的不同字符个数和每个字符的出现频率,利用统计数据构造构造哈夫曼树和哈夫曼编码 The Chinese official said he viewed the Trump Presidency not as an aberration but as the product of a ...
  • 任务过程:创建26个字母哈夫曼树,及其编码和译码 1、建立哈夫曼树 2、从每个叶结点回溯到root的路径,并记录路径,则为哈夫曼编码 3、查表方式获得每个字符的哈夫曼编码 -----------------------------------------...
  • 哈夫曼树原理,及构造方法

    万次阅读 多人点赞 2018-08-05 12:13:21
    哈夫曼树(最优二叉树) 百度百科:https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin 一. 目的: 找出存放一串字符所需的最少的二进制编码 二. 构造方法: 首先统计出每...
  • 哈夫曼树构造算法想必我们大家都是耳熟能详的,对于大多数的题目都可以轻松构造出来,但是,我们也知道哈夫曼树的构造有的简单,有的较难,存在多种情况。 我们首先看哈夫曼树的构造方法描述 (1)、根据 n 个给定...
  • Java小项目之哈夫曼树与文件压缩和解压缩(一)哈夫曼树构造 前言:在了解哈夫曼树之前,我们还是先看下树的相关知识吧! 一、数据结构中树的相关知识 数据结构是计算机存储、组织数据的方式。数据结构是指...
  • 哈夫曼树&算法&编码

    千次阅读 2020-08-06 09:31:23
    哈夫曼树 哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树...
  • 哈夫曼树构造及编码

    千次阅读 2015-06-22 23:42:20
    哈夫曼树: 树的带权路径长度是树中所有叶子结点的带权路径长度之和。...哈夫曼算法给出了构造哈夫曼树的基本思想: 1.给出n个权值各异的结点作为n颗二叉树的根结点,左右子树均空,组成二叉树集合F;
  • 哈夫曼树算法实现

    2019-11-28 11:23:36
    #include <stdio.h> #include<stdlib.h> #include <conio.h> #include <string.h>...#define n 5 // 定义...#define m 9 // 哈夫曼树结点用一个大小为2n-1 的向量存储 typedef struct { i...

空空如也

空空如也

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

哈夫曼树构造算法