精华内容
下载资源
问答
  • 哈夫曼树和哈夫曼树编码

    千次阅读 2014-05-28 14:50:01
    和哈夫曼编码哈夫曼编码哈夫曼树的一个应用。哈夫曼编码应用广泛,如 JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树哈夫曼树又称最优二叉树, 是一种带权路径长度最短的二叉树。所谓树的带权...

    在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)

    树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如

    JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树,

    是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点

    的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度

    为叶结点的层数)。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)

    ,N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径

    长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

    哈夫曼编码步骤:

    一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列。)
    二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
    三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
    四、重复二和三两步,直到集合F中只有一棵二叉树为止。

    简易的理解就是,假如我有A,B,C,D,E五个字符,出现的频率(即权值)分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取1,2构成新树,其结点为1+2=3,如图:

    12

    虚线为新生成的结点,第二步再把新生成的权值为3的结点放到剩下的集合中,所以集合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树,如图:

    13

    再依次建立哈夫曼树,如下图:

    14

    其中各个权值替换对应的字符即为下图:

    15

    所以各字符对应的编码为:A->11,B->10,C->00,D->011,E->010

    霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合。

     

    C语言代码实现:

    /*-------------------------------------------------------------------------
     * Name:   哈夫曼编码源代码。
     * Date:   2011.04.16
     * Author: Jeffrey Hill+Jezze(解码部分)
     * 在 Win-TC 下测试通过
     * 实现过程:着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 main()中
     *           自底向上开始(也就是从数组序号为零的结点开始)向上层层判断,若在
     *           父结点左侧,则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
     *------------------------------------------------------------------------*/
    #include <stdio.h>
    #include<stdlib.h>
     
    #define MAXBIT      100
    #define MAXVALUE  10000
    #define MAXLEAF     30
    #define MAXNODE    MAXLEAF*2 -1
     
    typedef struct 
    {
        int bit[MAXBIT];
        int start;
    } HCodeType;        /* 编码结构体 */
    typedef struct
    {
        int weight;
        int parent;
        int lchild;
        int rchild;
        int value;
    } HNodeType;        /* 结点结构体 */
     
    /* 构造一颗哈夫曼树 */
    void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)
    { 
        /* i、j: 循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
            x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
        int i, j, m1, m2, x1, x2;
        /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
        for (i=0; i<2*n-1; i++)
        {
            HuffNode[i].weight = 0;//权值 
            HuffNode[i].parent =-1;
            HuffNode[i].lchild =-1;
            HuffNode[i].rchild =-1;
            HuffNode[i].value=i; //实际值,可根据情况替换为字母  
        } /* end for */
     
        /* 输入 n 个叶子结点的权值 */
        for (i=0; i<n; i++)
        {
            printf ("Please input weight of leaf node %d: \n", i);
            scanf ("%d", &HuffNode[i].weight);
        } /* end for */
     
        /* 循环构造 Huffman 树 */
        for (i=0; i<n-1; i++)
        {
            m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
            x1=x2=0;
            /* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
            for (j=0; j<n+i; j++)
            {
                if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
                {
                    m2=m1; 
                    x2=x1; 
                    m1=HuffNode[j].weight;
                    x1=j;
                }
                else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
                {
                    m2=HuffNode[j].weight;
                    x2=j;
                }
            } /* end for */
                /* 设置找到的两个子结点 x1、x2 的父结点信息 */
            HuffNode[x1].parent  = n+i;
            HuffNode[x2].parent  = n+i;
            HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
            HuffNode[n+i].lchild = x1;
            HuffNode[n+i].rchild = x2;
     
            printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
            printf ("\n");
        } /* end for */
      /*  for(i=0;i<n+2;i++)
        {
            printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
                      }*///测试 
    } /* end HuffmanTree */
     
    //解码 
    void decodeing(char string[],HNodeType Buf[],int Num)
    {
      int i,tmp=0,code[1024];
      int m=2*Num-1;
      char *nump;
      char num[1024];
      for(i=0;i<strlen(string);i++)
      {
       if(string[i]=='0')
      num[i]=0;        
      else
      num[i]=1;                    
      } 
      i=0;
      nump=&num[0];
      
     while(nump<(&num[strlen(string)]))
     {tmp=m-1;
      while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
      {
      
       if(*nump==0)
       {
         tmp=Buf[tmp].lchild ;          
       } 
       else tmp=Buf[tmp].rchild;
       nump++;
            
      } 
      
      printf("%d",Buf[tmp].value);                                  
     }
     
      
    }
     
     
    int main(void)
    {
        
        HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
        HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组, 同时定义一个临时变量来存放求解编码时的信息 */
        int i, j, c, p, n;
        char pp[100];
        printf ("Please input n:\n");
        scanf ("%d", &n);
        HuffmanTree (HuffNode, n);
       
        
        for (i=0; i < n; i++)
        {
            cd.start = n-1;
            c = i;
            p = HuffNode[c].parent;
            while (p != -1)   /* 父结点存在 */
            {
                if (HuffNode[p].lchild == c)
                    cd.bit[cd.start] = 0;
                else
                    cd.bit[cd.start] = 1;
                cd.start--;        /* 求编码的低一位 */
                c=p;                    
                p=HuffNode[c].parent;    /* 设置下一循环条件 */
            } /* end while */
            
            /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
            for (j=cd.start+1; j<n; j++)
            { HuffCode[i].bit[j] = cd.bit[j];}
            HuffCode[i].start = cd.start;
        } /* end for */
        
        /* 输出已保存好的所有存在编码的哈夫曼编码 */
        for (i=0; i<n; i++)
        {
            printf ("%d 's Huffman code is: ", i);
            for (j=HuffCode[i].start+1; j < n; j++)
            {
                printf ("%d", HuffCode[i].bit[j]);
            }
            printf(" start:%d",HuffCode[i].start);
           
            printf ("\n");
            
        }
    /*    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            {
                 printf ("%d", HuffCode[i].bit[j]);           
            }
            printf("\n");
            }*/
        printf("Decoding?Please Enter code:\n");
        scanf("%s",&pp);
    decodeing(pp,HuffNode,n);
        getch();
        return 0;
    }
    展开全文
  • 哈夫曼树和哈夫曼树编码一、名词介绍二、哈夫曼树的基本概念三、构建哈夫曼树四、哈弗曼树中结点结构五、哈弗曼树中的查找算法六、构建哈弗曼树的代码实现七、哈夫曼编码八、完整代码(可运行)九、总结 一、名词...

    一、名词介绍

    (1)路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。图 1 中,从根结点到结点 a 之间的通路就是一条路径。

    (2)路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。

    (3)结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。例如,图 1 中结点 a 的权为 7,结点 b 的权为 5。

    (4)结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如,图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

    树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为:

    WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

    在这里插入图片描述

    二、哈夫曼树的基本概念

    当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”

    在构建哈弗曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近。在图 1 中,因为结点 a 的权值最大,所以理应直接作为根结点的孩子结点。

    三、构建哈夫曼树

    对于给定的有各自权值的 n 个结点,构建哈夫曼树有一个行之有效的办法:
    (1)在 n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和;
    (2)在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推;
    (3)重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是哈夫曼树。
    在这里插入图片描述
    上图中,(A)给定了四个结点a,b,c,d,权值分别为7,5,2,4;第一步如(B)所示,找出现有权值中最小的两个,2 和 4 ,相应的结点 c 和 d 构建一个新的二叉树,树根的权值为 2 + 4 = 6,同时将原有权值中的 2 和 4 删掉,将新的权值 6 加入;进入(C),重复之前的步骤。直到(D)中,所有的结点构建成了一个全新的二叉树,这就是哈夫曼树。

    四、哈弗曼树中结点结构

    构建哈夫曼树时,首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始,不断地构建新的父结点,直至树根,所以结点中应包含指向父结点的指针。但是在使用哈夫曼树时是从树根开始,根据需求遍历树中的结点,因此每个结点需要有指向其左孩子和右孩子的指针。

    所以,哈夫曼树中结点构成用代码表示为:

    //哈夫曼树结点结构
    typedef struct 
    {
      int weight;  //结点权重
      int parent, left, right;  //父结点、左孩子、右孩子在数组中的位置下标
    }HTNode, *HuffmanTree;

    五、哈弗曼树中的查找算法

    构建哈夫曼树时,需要每次根据各个结点的权重值,筛选出其中值最小的两个结点,然后构建二叉树。

    查找权重值最小的两个结点的思想是:从树组起始位置开始,首先找到两个无父结点的结点(说明还未使用其构建成树),然后和后续无父结点的结点依次做比较,有两种情况需要考虑:

    (1)如果比两个结点中较小的那个还小,就保留这个结点,删除原来较大的结点;
    (2)如果介于两个结点权重值之间,替换原来较大的结点;

    代码实现:

    //HT数组中存放的哈夫曼树,end表示HT数组中存放结点的最终位置,s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
    void Select(HuffmanTree HT, int end, int *s1, int *s2)
    {
      int min1, min2;
      //遍历数组初始下标为 1
      int i = 1;
      //找到还没构建树的结点
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      min1 = HT[i].weight;
      *s1 = i;
      i++;
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      //对找到的两个结点比较大小,min2为大的,min1为小的
      if(HT[i].weight < min1)
      {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
      }
      else
      {
        min2 = HT[i].weight;
        *s2 = i;
      }
      //两个结点和后续的所有未构建成树的结点做比较
      for(int j=i+1; j <= end; j++)
      {
        //如果有父结点,直接跳过,进行下一个
        if(HT[j].parent != 0)
        {
          continue;
        }
        //如果比最小的还小,将min2=min1,min1赋值新的结点的下标
        if(HT[j].weight < min1)
        {
          min2 = min1;
          min1 = HT[j].weight;
          *s2 = *s1;
          *s1 = j;
        }
        //如果介于两者之间,min2赋值为新的结点的位置下标
        else if(HT[j].weight >= min1 && HT[j].weight < min2)
        {
          min2 = HT[j].weight;
          *s2 = j;
        }
      }
    }

    注意:s1和s2传入的是实参的地址,所以函数运行完成后,实参中存放的自然就是哈夫曼树中权重值最小的两个结点在数组中的位置。

    六、构建哈弗曼树的代码实现

    //HT为地址传递的存储哈夫曼树的数组,w为存储结点权重值的数组,n为结点个数
    void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
    {
      if(n <= 1) 
        return;   // 如果只有一个编码就相当于0
      int m = 2*n-1;   // 哈夫曼树总节点数,n就是叶子结点
      *HT = (HuffmanTree) malloc((m+1) * sizeof(HTNode));   // 0号位置不用
      HuffmanTree p = *HT;
      // 初始化哈夫曼树中的所有结点
      for(int i = 1; i <= n; i++)
      {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
      //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
      for(int i = n+1; i <= m; i++)
      {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
      //构建哈夫曼树
      for(int i = n+1; i <= m; i++)
      {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
      }
    }

    七、哈夫曼编码

    哈夫曼编码就是在哈夫曼树的基础上构建的,这种编码方式最大的优点就是用最少的字符包含最多的信息内容

    根据发送信息的内容,通过统计文本中相同字符的个数作为每个字符的权值,建立哈夫曼树。对于树中的每一个子树,统一规定其左孩子标记为 0 ,右孩子标记为 1 。这样,用到哪个字符时,从哈夫曼树的根结点开始,依次写出经过结点的标记,最终得到的就是该结点的哈夫曼编码。

    文本中字符出现的次数越多,在哈夫曼树中的体现就是越接近树根,编码的长度越短

    在这里插入图片描述
    如上图所示,字符 a 用到的次数最多,其次是字符 b 。字符 a 在哈夫曼编码是 0 ,字符 b 编码为 10 ,字符 c 的编码为 110 ,字符 d 的编码为 111 。

    使用程序求哈夫曼编码有两种方法:

    1)从叶子结点一直找到根结点,逆向记录途中经过的标记。
    例如,图 3中字符 c 的哈夫曼编码从结点 c 开始一直找到根结点,结果为:0 1 1 ,所以字符 c 的哈夫曼编码为:1 1 0(逆序输出)。
    
    (2)从根结点出发,一直到叶子结点,记录途中经过的标记。
    例如,求图 中字符 c 的哈夫曼编码,就从根结点开始,依次为:1 1 0

    采用方法(1)的实现代码为:

    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符串数组
      cd[n-1] = '\0';//字符串结束符
      for(int i=1; i<=n; i++)
      {
        //从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
        int start = n-1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while(j != 0)
        {
          // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
          if(HT[j].left == c)
            cd[--start] = '0';
          else
            cd[--start] = '1';
          //以父结点为孩子结点,继续朝树根的方向遍历
          c = j;
          j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i], &cd[start]);
      }
      //使用malloc申请的cd动态数组需要手动释放
      free(cd);
    }

    采用方法(2)的实现代码为:

    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      int m = 2*n-1;
      int p = m;
      int cdlen = 0;
      char *cd = (char *)malloc(n*sizeof(char));
      //将各个结点的权重用于记录访问结点的次数,首先初始化为0
      for (int i=1; i<=m; i++) 
      {
        HT[i].weight = 0;
      }
      //一开始 p 初始化为 m,也就是从树根开始。一直到p为0
      while (p) 
      {
        //如果当前结点一次没有访问,进入这个if语句
        if (HT[p].weight == 0) 
        {
          HT[p].weight = 1;  //重置访问次数为1
          //如果有左孩子,则访问左孩子,并且存储走过的标记为0
          if (HT[p].left != 0) 
          {
            p = HT[p].left;
          }
          else if(HT[p].right == 0) // 当前结点没有左孩子,也没有右孩子,说明为叶子结点,直接记录哈夫曼编码
          {
            (*HC)[p] = (char*)malloc((cdlen+1)*sizeof(char));
            cd[cdlen] = '\0';
            strcpy((*HC)[p], cd);
          }
        }
        else if(HT[p].weight == 1) // 如果weiget为1,说明访问过一次,即使是左孩子返回的
        {
          HT[p].weight = 2;  //设置访问次数为2
          //如果有右孩子,遍历右孩子,记录标记值 1
          if (HT[p].right != 0) 
          {
            p = HT[p].right;
            cd[cdlen++] = '1';
          }
        }
        else //如果访问次数为2,说明左孩子都遍历完了,返回父结点
        {
          HT[p].weight = 0;
          p = HT[p].parent;
          --cdlen;
        }
      }
    }

    八、完整代码(可运行)

    #include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    
    //哈夫曼树结点结构
    typedef struct 
    {
      int weight;//结点权重
      int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
    }HTNode, *HuffmanTree;
    //动态二维数组,存储哈夫曼编码
    typedef char **HuffmanCode;
    //HT数组中存放的哈夫曼树,end表示HT数组中存放结点的最终位置,s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
    void Select(HuffmanTree HT, int end, int *s1, int *s2)
    {
      int min1, min2;
      //遍历数组初始下标为 1
      int i = 1;
      //找到还没构建树的结点
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      min1 = HT[i].weight;
      *s1 = i;
      i++;
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      //对找到的两个结点比较大小,min2为大的,min1为小的
      if(HT[i].weight < min1)
      {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
      }
      else
      {
        min2 = HT[i].weight;
        *s2 = i;
      }
      //两个结点和后续的所有未构建成树的结点做比较
      for(int j=i+1; j <= end; j++)
      {
        //如果有父结点,直接跳过,进行下一个
        if(HT[j].parent != 0)
        {
          continue;
        }
        //如果比最小的还小,将min2=min1,min1赋值新的结点的下标
        if(HT[j].weight < min1)
        {
          min2 = min1;
          min1 = HT[j].weight;
          *s2 = *s1;
          *s1 = j;
        }
        else if(HT[j].weight >= min1 && HT[j].weight < min2)   // 如果介于两者之间,min2赋值为新的结点的位置下标
        {
          min2 = HT[j].weight;
          *s2 = j;
        }
      }
    }
    
    //HT为地址传递的存储哈夫曼树的数组,w为存储结点权重值的数组,n为结点个数
    void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
    {
      if(n<=1) 
        return;     // 如果只有一个编码就相当于0
      int m = 2*n-1;   // 哈夫曼树总节点数,n就是叶子结点
      *HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号位置不用
      HuffmanTree p = *HT;
      // 初始化哈夫曼树中的所有结点
      for(int i = 1; i <= n; i++)
      {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
    
      //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
      for(int i = n+1; i <= m; i++)
      {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
    
      //构建哈夫曼树
      for(int i = n+1; i <= m; i++)
      {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
      }
    }
    
    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符串数组
      cd[n-1] = '\0';//字符串结束符
      for(int i=1; i<=n; i++)
      {
        //从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
        int start = n-1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while(j != 0)
        {
          // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
          if(HT[j].left == c)
            cd[--start] = '0';
          else
            cd[--start] = '1';
          //以父结点为孩子结点,继续朝树根的方向遍历
          c = j;
          j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i], &cd[start]);
      }
      //使用malloc申请的cd动态数组需要手动释放
      free(cd);
    }
    
    //打印哈夫曼编码的函数
    void PrintHuffmanCode(HuffmanCode htable, int *w, int n)
    {
      printf("Huffman code : \n");
      for(int i = 1; i <= n; i++)
        printf("%d code = %s\n",w[i-1], htable[i]);
    }
    
    int main(void)
    {
      int w[5] = {2, 8, 7, 6, 5};
      int n = 5;
      HuffmanTree htree;
      HuffmanCode htable;
      CreateHuffmanTree(&htree, w, n);
      HuffmanCoding(htree, &htable, n);
      PrintHuffmanCode(htable, w, n);
    
      return 0;
    }

    运行结果:

    Huffman code :
    2 code = 100
    8 code = 11
    7 code = 01
    6 code = 00
    5 code = 101

    九、总结

    程序运行效果图如下:
    在这里插入图片描述
    本节的程序中对权重值分别为 2,8,7,6,5 的结点构建的哈夫曼树如上图(A)所示。图 中(B)是另一个哈夫曼树,两棵树的带权路径长度相同。

    程序运行效果图之所以是(A)而不是(B),原因是在构建哈夫曼树时,结点 2 和结点 5 构建的新的结点 7 存储在动态树组的最后面,所以,在程序继续选择两个权值最小的结点时,直接选择了的叶子结点 6 和 7 。

    展开全文
  • 哈夫曼树哈夫曼树编码

    千次阅读 2015-09-09 15:50:57
    和哈夫曼编码哈夫曼编码哈夫曼树的一个应用。哈夫曼编码应用广泛,如 JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树哈夫曼树又称最优二叉树, 是一种带权路径长度最短的二叉树。所谓树的带权...

    本文转自哈夫曼树及哈夫曼树编码

    在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)

    树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如

    JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树,

    是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点

    的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度

    为叶结点的层数)。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)

    ,N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径

    长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

    哈夫曼编码步骤:

    一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列。)
    二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
    三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
    四、重复二和三两步,直到集合F中只有一棵二叉树为止。

    简易的理解就是,假如我有A,B,C,D,E五个字符,出现的频率(即权值)分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取1,2构成新树,其结点为1+2=3,如图:

    12

    虚线为新生成的结点,第二步再把新生成的权值为3的结点放到剩下的集合中,所以集合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树,如图:

    13

    再依次建立哈夫曼树,如下图:

    14

    其中各个权值替换对应的字符即为下图:

    15

    所以各字符对应的编码为:A->11,B->10,C->00,D->011,E->010

    霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合。

     

    C语言代码实现:

    /*-------------------------------------------------------------------------
     * Name:   哈夫曼编码源代码。
     * Date:   2011.04.16
     * Author: Jeffrey Hill+Jezze(解码部分)
     * 在 Win-TC 下测试通过
     * 实现过程:着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 main()中
     *           自底向上开始(也就是从数组序号为零的结点开始)向上层层判断,若在
     *           父结点左侧,则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
     *------------------------------------------------------------------------*/
    #include <stdio.h>
    #include<stdlib.h>
     
    #define MAXBIT      100
    #define MAXVALUE  10000
    #define MAXLEAF     30
    #define MAXNODE    MAXLEAF*2 -1
     
    typedef struct 
    {
        int bit[MAXBIT];
        int start;
    } HCodeType;        /* 编码结构体 */
    typedef struct
    {
        int weight;
        int parent;
        int lchild;
        int rchild;
        int value;
    } HNodeType;        /* 结点结构体 */
     
    /* 构造一颗哈夫曼树 */
    void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)
    { 
        /* i、j: 循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
            x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
        int i, j, m1, m2, x1, x2;
        /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
        for (i=0; i<2*n-1; i++)
        {
            HuffNode[i].weight = 0;//权值 
            HuffNode[i].parent =-1;
            HuffNode[i].lchild =-1;
            HuffNode[i].rchild =-1;
            HuffNode[i].value=i; //实际值,可根据情况替换为字母  
        } /* end for */
     
        /* 输入 n 个叶子结点的权值 */
        for (i=0; i<n; i++)
        {
            printf ("Please input weight of leaf node %d: \n", i);
            scanf ("%d", &HuffNode[i].weight);
        } /* end for */
     
        /* 循环构造 Huffman 树 */
        for (i=0; i<n-1; i++)
        {
            m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
            x1=x2=0;
            /* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
            for (j=0; j<n+i; j++)
            {
                if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
                {
                    m2=m1; 
                    x2=x1; 
                    m1=HuffNode[j].weight;
                    x1=j;
                }
                else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
                {
                    m2=HuffNode[j].weight;
                    x2=j;
                }
            } /* end for */
                /* 设置找到的两个子结点 x1、x2 的父结点信息 */
            HuffNode[x1].parent  = n+i;
            HuffNode[x2].parent  = n+i;
            HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
            HuffNode[n+i].lchild = x1;
            HuffNode[n+i].rchild = x2;
     
            printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
            printf ("\n");
        } /* end for */
      /*  for(i=0;i<n+2;i++)
        {
            printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
                      }*///测试 
    } /* end HuffmanTree */
     
    //解码 
    void decodeing(char string[],HNodeType Buf[],int Num)
    {
      int i,tmp=0,code[1024];
      int m=2*Num-1;
      char *nump;
      char num[1024];
      for(i=0;i<strlen(string);i++)
      {
       if(string[i]=='0')
      num[i]=0;        
      else
      num[i]=1;                    
      } 
      i=0;
      nump=&num[0];
      
     while(nump<(&num[strlen(string)]))
     {tmp=m-1;
      while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
      {
      
       if(*nump==0)
       {
         tmp=Buf[tmp].lchild ;          
       } 
       else tmp=Buf[tmp].rchild;
       nump++;
            
      } 
      
      printf("%d",Buf[tmp].value);                                  
     }
     
      
    }
     
     
    int main(void)
    {
        
        HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
        HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组, 同时定义一个临时变量来存放求解编码时的信息 */
        int i, j, c, p, n;
        char pp[100];
        printf ("Please input n:\n");
        scanf ("%d", &n);
        HuffmanTree (HuffNode, n);
       
        
        for (i=0; i < n; i++)
        {
            cd.start = n-1;
            c = i;
            p = HuffNode[c].parent;
            while (p != -1)   /* 父结点存在 */
            {
                if (HuffNode[p].lchild == c)
                    cd.bit[cd.start] = 0;
                else
                    cd.bit[cd.start] = 1;
                cd.start--;        /* 求编码的低一位 */
                c=p;                    
                p=HuffNode[c].parent;    /* 设置下一循环条件 */
            } /* end while */
            
            /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
            for (j=cd.start+1; j<n; j++)
            { HuffCode[i].bit[j] = cd.bit[j];}
            HuffCode[i].start = cd.start;
        } /* end for */
        
        /* 输出已保存好的所有存在编码的哈夫曼编码 */
        for (i=0; i<n; i++)
        {
            printf ("%d 's Huffman code is: ", i);
            for (j=HuffCode[i].start+1; j < n; j++)
            {
                printf ("%d", HuffCode[i].bit[j]);
            }
            printf(" start:%d",HuffCode[i].start);
           
            printf ("\n");
            
        }
    /*    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            {
                 printf ("%d", HuffCode[i].bit[j]);           
            }
            printf("\n");
            }*/
        printf("Decoding?Please Enter code:\n");
        scanf("%s",&pp);
    decodeing(pp,HuffNode,n);
        getch();
        return 0;
    }

    展开全文
  • 数据结构实验:通过输入结点数结点权值,输出哈夫曼树各结点左右子树,生成哈夫曼编码哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,可变字长编码(VLC)的一种。
  • 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);
        }
    
    }
    

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

    展开全文
  • 构造哈夫曼树和生成哈夫曼编码

    万次阅读 多人点赞 2019-01-25 17:12:36
    一、什么是哈夫曼树哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。用一幅图来说明: 它们的带权路径长度分别为: 图a: WPL=5*2+7*2+2*2+13*2=54 图b: WPL=5*3+2*3+7*2+13*1=48 可见,图b...
  • 哈夫曼树的创建,哈夫曼编码哈夫曼译码C语言实现代码 哈夫曼树的创建哈夫曼编码哈夫曼译码C语言实现代码markdown书写的html格式 如果需要将文件编码或译码,则应该加入文件操作,将文件的字符读入。其权重应该为...
  • 哈夫曼树哈夫曼编码详解【完整版代码

    万次阅读 多人点赞 2018-06-17 11:42:30
    赫夫曼(Huffman Tree),又称最优二叉树,是一类带权路径长度最短的。假设有n个权值{w1,w2,…,wn},如果构造一棵有n个叶子节点的二叉树,而这n个叶子节点的权值是{w1,w2,…,wn},则所构造出的带权路径长度最小...
  • 哈夫曼树的创建和编码

    万次阅读 多人点赞 2016-03-19 21:30:16
    哈夫曼树的创建和编码      1.哈夫曼树又称最优二叉树,是一类带权路径长度最短的树。  对于最优二叉树,权值越大的结点越接近树的根结点,权值越小的结点越远离树的根结点。  最优二叉树的构造算法步骤:  ...
  • 哈夫曼树
  • 构造哈夫曼树,并生成编码 构造哈夫曼树,并生成编码
  • 我们通过一个具体的实例来讲解哈夫曼树的构造以及编码反编码。 比如说我们要对一字符串进行01编码,该如何做?我们要清楚为什么要使用哈夫曼编码?答案很简单,哈夫曼编码占位可以做到最少。 一、给出指定字符串...
  • 题目:哈夫曼树和哈夫曼编码:从终端输入若干个字符,...最后打印哈夫曼树和对应的哈夫曼编码代码如下://^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^#incl...
  • 最优二叉树--哈夫曼树和最优前缀编码--哈夫曼编码

    万次阅读 多人点赞 2017-05-18 11:56:25
    1.最优二叉树的定义最优二叉树又称哈夫曼树,是一种带权路径长最短的树。树的路径长度是从树根到每一个叶子之间的路径长度之。节点的带树路径长度为从该节点到树根之间的路径长度与该节点权(比如字符在某串中的...
  • void Code() 哈夫曼树编码 void Encode() 哈夫曼树解码 void WPL() 计算带权路径长度 所选实例: 所选实例 创建哈夫曼树 步骤: 假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、...
  • #include<stdio.h> #define n 8 #define m (2*n-1) //创建结点结构体 typedef struct huffnode { int weight; int parent; int lchild; int rchild; }huffnode; //创建每个字母的结构体 ...//存放每一个
  • 举例理解哈夫曼树哈夫曼编码

    万次阅读 2020-07-02 08:52:56
    举例理解哈夫曼树,C语言实现哈夫曼树
  • 文章目录哈夫曼树的构建及编码一、什么是哈夫曼树二、什么是哈夫曼编码三、怎么建哈夫曼树、求哈夫曼编码四、为什么哈夫曼编码能实现压缩 声明:关于文件压缩,不是本文的重点,本文只说明并讨论哈夫曼树的构建...
  • 哈夫曼树和哈夫曼编码(附完整C语言代码)

    千次阅读 多人点赞 2020-12-02 23:42:06
    哈夫曼树,也叫最优二叉树。在含有给定的n个带权叶子结点的二叉树中,WPL最小的树。其中,结点的权指的是某种特定含义的数值;带权路径长度值根到结点的路径长度乘以结点权值;树的带权路径长度(WPL)是指树中所有...
  • 哈夫曼树哈夫曼编码代码实现

    千次阅读 多人点赞 2020-03-18 12:43:30
    哈夫曼树哈夫曼编码的理解 数据压缩 含义 通过对数据重新的编码,减少数据占用的空间存储;使用的时候再进行解压缩,恢复数据的原有特性。 类别 无损压缩——压缩过程没有数据丢失,解压得到原有数据特性。 有损...
  • 一般来说如果只是要求最小帯权路径长度,不一定要构造哈夫曼树,直接用一个优先队列就可以模拟这个过程,但是如果需要实现哈夫曼编码,这时就必须得构建哈夫曼树了。 由定义哈夫曼树是二叉树,那分析,构建哈夫曼树...
  • 哈夫曼树&&哈夫曼编码 1、源代码(详解见注释) #include <stdio.h> #include<stdlib.h> #include<string.h> typedef struct { int weight; int parent,lchild,rchild; }HTNode,*...
  • 介绍哈夫曼树哈夫曼编码
  • 哈夫曼树和哈夫曼编码详解(C语言实现)

    万次阅读 多人点赞 2020-04-15 12:36:48
    赫夫曼树,别名“哈夫曼树”、“最优树”以及“最优二叉树”。学习哈夫曼树之前,首先要了解几个名词。 哈夫曼树相关的几个名词 路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。图1 中,从根结点到...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,452
精华内容 2,980
关键字:

哈夫曼树和哈夫曼编码代码