精华内容
参与话题
问答
  • 哈夫曼树(霍夫曼树)-详解

    千次阅读 2018-07-14 19:02:55
    哈夫曼树(霍夫曼树)-详解 哈夫曼树(霍夫曼树)-详解 权值 哈夫曼树(霍夫曼树)介绍 在了解哈佛曼树前,需要先了解,何为权值,何为路径,以及权值计算。 权值 何为权值?我们看下百度百科的解释。 ...

    哈夫曼树(霍夫曼树)-详解

    在了解哈佛曼树前,需要先了解,何为权值,何为路径,以及权值计算。

    何为权值?我们看下百度百科的解释。

    by:百度百科
    在数学领域,权值指加权平均数中的每个数的频数,也称为权数或权重。
    计算机领域中(数据结构)
    权值就是定义的路径上面的值。可以这样理解为结点间的距离。通常指字符对应的二进制编码出现的概率。
    至于[哈夫曼树]中的权值可以理解为:权值大表明出现概率大!
    一个结点的权值实际上就是这个结点子树在整个树中所占的比例.
    abcd四个[叶子结点]的权值为7,5,2,4, 这个7,5,2,4是根据实际情况得到的,比如说从一段文本中统计出abcd四个字母出现的次数分别为7,5,2,4. 说a结点的权值为7,意思是说a结点在系统中占有7这个份量。实际上也可以化为百分比来表示,但反而麻烦,实际上是一样的。

    何为路径?

    连接两个节点的线就是路径。

    何为路径长度?

    从顶点到 1,其需要经过 a 、b 路径。那么路径长度就为2

    何为树的路径长度?

    从树的顶点,到各个节点的路径长度总和,即为树的路径长度。

    何为结点的带权路径长度?

    结点权即为本身数值,而结点的带权路径长度为从树的订单到结点的路径长度与结点的权 数值乘积。
    公式: 结点的带权路径长度 = 结点的路径长度 * 结点的带权值

    例:上图,从顶点到对应结点,那么它的带权路径长度为 2 x 100 = 200

    何为树的带权路径长度(WPL)?

    树的带权路径长度为结点的带权路径长度之和。可参考上图。

    哈夫曼树(霍夫曼树)介绍

    by: 百度百科
    给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    一个二叉树的带权路径长度(WPL)最小,才能为哈夫曼树。而要使得WPL最小,则需要结点权值最大越靠近顶点,而结点权值越小离顶点越远。
    以下为图示的简单例子:

    package com.base.data.tree;
    /**
     * 创建一个结点,包含权重信息 * @param <E>
      */
    public class HuffTreeNode<E> {
        E data;
        double weight;
        HuffTreeNode leftNode;
        HuffTreeNode rightNode;
    
        public HuffTreeNode(E data,double weight) {
            this.data = data;
            this.weight = weight;
        }
    
        public HuffTreeNode(E data, double weight, HuffTreeNode leftNode, HuffTreeNode rightNode) {
            this.data = data;
            this.weight = weight;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
        }
    }
    package com.base.data.tree;
    
    import java.util.*;
    
    public class HuffTree {
    
        /**
         * 创建哈夫曼树 
         * @param huffTreeNodeList {@link HuffTreeNode}
         * @return 返回树
         */  
        public HuffTreeNode createHuffTree(List<HuffTreeNode> huffTreeNodeList){
            while(huffTreeNodeList.size() > 1){
                //排序
      sortHuffTrees(huffTreeNodeList);
                int size = huffTreeNodeList.size();
                //从尾部开始循环
      HuffTreeNode leftNode = huffTreeNodeList.get(size-1);
                HuffTreeNode rightNode = huffTreeNodeList.get(size-2);
                //创建父结点
      HuffTreeNode parentNode = new HuffTreeNode(null,leftNode.weight+rightNode.weight);
                parentNode.leftNode = leftNode;
                parentNode.rightNode = rightNode;
    
                huffTreeNodeList.remove(size-1);
                huffTreeNodeList.remove(size-2);
    
                huffTreeNodeList.add(parentNode);
            }
            return huffTreeNodeList.get(0);
        }
    
        /**
         * 冒泡排序 结点的权重信息 从大到小 
         * @param huffTreeNodeList
        */
      public void sortHuffTrees(List<HuffTreeNode> huffTreeNodeList){
            int i = huffTreeNodeList.size()-1;
            while (i > 0){
                int post = 0;
                for (int i1 = 0; i1 < i; i1++) {
                    if(huffTreeNodeList.get(i1).weight < huffTreeNodeList.get(i1+1).weight){
                        post = i1;
                        HuffTreeNode temp = huffTreeNodeList.get(i1+1);
                        huffTreeNodeList.set(i1+1,huffTreeNodeList.get(i1));
                        huffTreeNodeList.set(i1,temp);
                    }
                }
                i = post;
            }
        }
    
        public void printNode(HuffTreeNode huffTreeNode){
            System.out.println(huffTreeNode.weight);
            if(huffTreeNode.leftNode != null){
                System.out.println(huffTreeNode.leftNode.weight);
                printNode(huffTreeNode.leftNode);
            }
            if(huffTreeNode.rightNode != null){
                System.out.println(huffTreeNode.rightNode.weight);
                printNode(huffTreeNode.rightNode);
            }
        }
    
        public static void main(String[] args) {
            HuffTree huffTree = new HuffTree();
            List<HuffTreeNode> huffTreeNodeList = new ArrayList<>();
            for(int i=0;i<1000;i++){
                Random random = new Random();
                double randomDouble = random.nextInt(100000);
                huffTreeNodeList.add(new HuffTreeNode("A结点"+i, randomDouble));
            }
            huffTree.createHuffTree(huffTreeNodeList);
            huffTree.printNode(huffTreeNodeList.get(0));
        }
    }
    展开全文
  • 霍夫曼树(最优二叉树)简介

    千次阅读 2017-05-04 20:01:09
     说到霍夫曼树,就不得不提霍夫曼编码(Huffman Coding)。霍夫曼编码是可变字长编码(VLC)的一种。David.A.Huffman于1952年提出该编码方法,即完全依据字符出现概率来构造异字头的平均长度最短的码字,亦称之为最佳...

    一、霍夫曼编码

          说到霍夫曼树,就不得不提霍夫曼编码(Huffman Coding)。霍夫曼编码是可变字长编码(VLC)的一种。David.A.Huffman于1952年提出该编码方法,即完全依据字符出现概率来构造异字头的平均长度最短的码字,亦称之为最佳编码。

          在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符。例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R,T,F,D”,各字母出现的次数为{8,4,5,3,1,1}。现要求为这些字母设计编码。要区别6个字母,最简单的二进制编码方式是等长编码,固定采用3位二进制,可分别用000、001、010、011、100、101对“A,E,R,T,F,D”进行编码发送,当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符,则固定编码长度为5。然而,传送报文时总是希望总长度尽可能短。

          在实际应用中,各个字符的出现频度或使用次数是不相同的,如A、B、C的使用频率远远高于X、Y、Z,自然会想到设计编码时,如果能让出现频率高的字符的编码长度减少,频率低的字符编码长度 长于 频率高的。这样整个信息的编码长度会减少,并且能区分出不同的字符。

          为了实现这种更高效的编码方式,就需要利用一个二叉树的结构来进行辅助编码,这种二叉树即为霍夫曼树,也称作最优二叉树。来实现一个字符的编码不是另一个字符编码的前缀。


    二、霍夫曼树的定义与算法描述

             在说明霍夫曼树之前,需要介绍几个术语。

          1、路径和路径长度
          在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。
          2、结点的权及带权路径长度
          若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积
          3、树的带权路径长度
          树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。(Weighted Path Length of Tree)


          所谓赫夫曼树,就是带权路径长度之和WPL最小的那个二叉树。(因此也叫作最优二叉树)

        

         一般来说,用n(n>0)个带权值的叶子来构造二叉树,限定二叉树中除了这n个叶子外只能出现度为2的结点


         算法描述

         

          

         

          例如


    三、霍夫曼编码的实现

    http://blog.csdn.net/feynman1999/article/details/71178357

         


    展开全文
  • 霍夫曼树及霍夫曼编码的C语言实现

    万次阅读 多人点赞 2016-05-08 21:15:32
    从周五开始学习霍夫曼树,一直到今天终于完成,期间遇到了各种各样的棘手的问题,通过一遍遍在纸上分析每一步的具体状态得以解决。现在对学习霍夫曼树的过程加以记录首先介绍霍夫曼树霍夫曼树(Huffman Tree),又称...

    从周五开始学习霍夫曼树,一直到今天终于完成,期间遇到了各种各样的棘手的问题,通过一遍遍在纸上分析每一步的具体状态得以解决。现在对学习霍夫曼树的过程加以记录

    首先介绍霍夫曼树

    霍夫曼树(Huffman Tree),又称最优二叉树,是一类带权路径长度最短的树。假设有n个权值{w1,w2,…,wn},如果构造一棵有n个叶子节点的二叉树,而这n个叶子节点的权值是{w1,w2,…,wn},则所构造出的带权路径长度最小的二叉树就被称为赫夫曼树。

    这里补充下树的带权路径长度的概念。树的带权路径长度指树中所有叶子节点到根节点的路径长度与该叶子节点权值的乘积之和,如果在一棵二叉树中共有n个叶子节点,用Wi表示第i个叶子节点的权值,Li表示第i个也叶子节点到根节点的路径长度,则该二叉树的带权路径长度 WPL=W1*L1 + W2*L2 + … Wn*Ln。

    根据节点的个数以及权值的不同,赫夫曼树的形状也各不相同,赫夫曼树具有如下特性:

    对于同一组权值,所能得到的霍夫曼树不一定是唯一的。
    赫夫曼树的左右子树可以互换,因为这并不影响树的带权路径长度。
    带权值的节点都是叶子节点,不带权值的节点都是某棵子二叉树的根节点。
    权值越大的节点越靠近赫夫曼树的根节点,权值越小的节点越远离赫夫曼树的根节点。
    赫夫曼树中只有叶子节点和度为2的节点,没有度为1的节点。
    一棵有n个叶子节点的赫夫曼树共有2n-1个节点。

    赫夫曼树的构建步骤如下:
    1、将给定的n个权值看做n棵只有根节点(无左右孩子)的二叉树,组成一个集合HT,每棵树的权值为该节点的权值。
    2、从集合HT中选出2棵权值最小的二叉树,组成一棵新的二叉树,其权值为这2棵二叉树的权值之和。
    3、将步骤2中选出的2棵二叉树从集合HT中删去,同时将步骤2中新得到的二叉树加入到集合HT中。
    4、重复步骤2和步骤3,直到集合HT中只含一棵树,这棵树便是赫夫曼树。
    这里写图片描述

    假如给定如下5个权值:
    
    
    则按照以上步骤,可以构造出如下面左图所示的赫夫曼树,当然也可能构造出如下面右图所示的赫夫曼树,这并不是唯一的。
    

    Huffman编码
    赫夫曼树的应用十分广泛,比如众所周知的在通信电文中的应用。在等传送电文时,我们希望电文的总长尽可能短,因此可以对每个字符设计长度不等的编码,让电文中出现较多的字符采用尽可能短的编码。为了保证在译码时不出现歧义,我们可以采取如下图所示的编码方式:


    即左分支编码为字符0,右分支编码为字符1,将从根节点到叶子节点的路径上分支字符组成的字符串作为叶子节点字符的编码,这便是赫夫曼编码。我们根据上面左图可以得到各叶子节点的赫夫曼编码如下:
    权值为5的也自己节点的赫夫曼编码为:11
    权值为4的也自己节点的赫夫曼编码为:10
    权值为3的也自己节点的赫夫曼编码为:00
    权值为2的也自己节点的赫夫曼编码为:011
    权值为1的也自己节点的赫夫曼编码为:010

    而对于上面右图,则可以得到各叶子节点的赫夫曼编码如下:
    权值为5的也自己节点的赫夫曼编码为:00
    权值为4的也自己节点的赫夫曼编码为:01
    权值为3的也自己节点的赫夫曼编码为:10
    权值为2的也自己节点的赫夫曼编码为:110
    权值为1的也自己节点的赫夫曼编码为:111
    

    下面给出C语言实现

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    typedef int Status;
    /*定义霍夫曼树节点*/
    typedef struct HTNode{
        int parent;/*记录双亲*/ 
        int Lchild;/*左右子树*/ 
        int Rchild;
        int Weight;/*记录权重*/ 
    }HTNode;
    typedef struct HTNode * HuffmanTree;
    typedef char ** HuffmanCode;
    
    /*在前k棵树种找到权重最小的树*/
    int Min(HuffmanTree HT,int k){
        int i=0,min_weight=0,min=0;
        /*找出第一个双亲存在的节点,将其权值赋值给min_weight*/
        /*注意此处不能直接将HT[0].weight赋给min_weight,原因是如果HT[0].weight最小,那么在第一次构造二叉树时就会被选走,而后续的每一轮选择最小权值构造二叉树的比较
        还是先用HT[0].weight的值来进行判断,这样又会再次将其选走,从而产生逻辑上的错误。*/
        while(HT[i].parent!=-1)
           i++;
        min_weight=HT[i].Weight;
        min=i;
        for(i;i<k;i++){
            if(HT[i].Weight<min_weight&&HT[i].parent==-1){
                min_weight=HT[i].Weight;
                min=i;
            }
        }
        /*找到最小权重的树,将其双亲置为1*/ 
        /*!!!!!注意这的HT的下标!!!!!一晚上才找出这个小问题,别写成HT[i]!!!!!!*/ 
        HT[min].parent=1;
        return min;
    }
    
    /*从前k棵树中选出权重最小的两棵树,将其序号赋给min1和min2*/ 
    Status SelectMin(HuffmanTree HT,int k,int &min1,int &min2){
        min1=Min(HT,k);
        min2=Min(HT,k);
        return OK; 
    } 
    
    
    /*创建一课霍夫曼树,-1表示不存在*/
    /*wet为一个记录权重的数组,类型为int*/ 
    HuffmanTree CreateHuffmanTree(HuffmanTree HT,int *wet,int n){
        int i=0;
        int total=2*n-1;/*有n个数据需要编码,即有n个叶子节点,也就有n-1个度为2的节点,总节点数为n+n-1=2*n-1*/ 
        /*初始状态下,前n个节点的双亲,左右子树应该均为-1,权重为对应的权重*/
        /*用HT的前n个分量存储n棵树(由n个待编码的数据组成)的森林*/ 
        /*申请total个int组成的动态数组*/
        HT=(HuffmanTree)malloc(total*sizeof(HTNode));
        if(!HT)
           return ERROR;
        for(i=0;i<n;i++){
            HT[i].Lchild=-1;
            HT[i].parent=-1;
            HT[i].Rchild=-1;
            HT[i].Weight=*wet;
            wet++;
        }
    
        /*对n到total的分量进行初始化*/ 
        for(i;i<total;i++){
            HT[i].Lchild=-1;
            HT[i].Rchild=-1;
            HT[i].parent=-1;
            HT[i].Weight=0; 
        }
        /*用HT的后n-1个分量存储霍夫曼树*/ 
        /*调用函数SelectMin找出森林中两棵权重最小的树*/ 
        int min1=0,min2=0; 
        for(i=n;i<total;i++){
            SelectMin(HT,i,min1,min2);
            HT[min1].parent=i;
            HT[min2].parent=i;
            HT[i].Lchild=min1;
            HT[i].Rchild=min2;
            HT[i].Weight=HT[min1].Weight+HT[min2].Weight;
        }
        return HT;
    } 
    
    /*从叶子节点开始逆向进行霍夫曼编码*/
    /*HC用来储存霍夫曼编码值*/
    Status HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n){
        /*HC本身是一个char类型数组的指针,其指向n个char类型的地址,所以给HC分配内存应该写成下面那样*/ 
        HC=(HuffmanCode)malloc(n*sizeof(char *));
        if(!HC)
           return ERROR;
        /*声明一个动态数组code,用来临时存储霍夫曼编码,数组含有n-1个霍夫曼码,加上一个'\0'终止符正好是n个元素,所以分配内存时*/ 
        char *code;
        code=(char *)malloc(n*sizeof(char));
        if(!code)
           return ERROR;
        code[n-1]='\0';/*让最后一个元素为终止符*/ 
    
        int i=0;
        for(i=0;i<n;i++){
            int current=i;
            int father=HT[i].parent;
            int start=n-1; 
            while(father!=-1){
                if(current==HT[father].Lchild)
                    code[--start]='0';
                else
                    code[--start]='1';
                current=father;
                father=HT[father].parent;
            }
            /*HC[i]用于最终存储霍夫曼码,是char类型的数组,有n个char类型的数据*/
            HC[i]=(char *)malloc((n-start)*sizeof(char));
            if(!HC[i])
                return ERROR;
            /*从临时空间中复制到HC[i]中*/
            strcpy(HC[i],code+start);
        }
        /*释放临时存储空间*/ 
        free(code);
        code=NULL;
        return OK; 
    }
    
    int main(void){
        int amount=0,i=0;
        int *wet=(int *)malloc(amount*sizeof(int));
        printf("请输入要编码的字符个数(个数为整型且>1)");
        scanf("%d",&amount); 
        while(amount<=1){
            printf("字符个数必须大于1\n");
            scanf("%d",&amount);
        }
        printf("请输入要编码的字符的权值");
        for(i=0;i<amount;i++){
            scanf("%d",wet+i);
        }
        HuffmanTree HT;
        HT=CreateHuffmanTree(HT,wet,amount);
    
        HuffmanCode HC;
        HuffmanCoding(HT,HC,amount);
        for(i=0;i<amount;i++){
            puts(HC[i]);
        }
        free(wet);
        return OK;
    }

    参考了http://blog.csdn.net/ns_code/article/details/19174553这篇博客

    2016-05-09更新:
    今日在复习霍夫曼树的过程中,发现自己忽视了一些细节问题,造成了一些错误,下面加以记录并反思

    问题一:出现在函数Min中

    int Min(HuffmanTree HT,int k){
        int min=0,min_weight=0,i=0;
        /*注意此处是先寻找双亲不存在的节点再赋值,给min_weight赋值应该在循环以外*/
        while(HT[i].parent!=-1)
            i++;
        min_weight=HT[i].weight;
        min=i;
        for(i;i<k;i++){
            if(HT[i].weight<min_weight&&HT[i].parent==-1){
                min_weight=HT[i].weight;
                min=i;
            }
        }
        /*赋值之后切记要将其双亲赋值为1,否则会出现错误*/ 
        HT[min].parent=1;
        return min;
    }

    问题二:出现在CreateHuffmanTree函数中

    HuffmanTree CreateHuffmanTree(HuffmanTree HT,int * wet,int amount){
        int i=0,min_weight=0,min=0;
        int total=2*amount-1;
        /*注意此处分配内存时,sizeof()中应该是HTNode!!要对HT的本质进行理解,HT是一棵树!*/ 
        HT=(HuffmanTree)malloc(total*sizeof(HTNode));
        if(!HT)
           return ERROR;
        for(i=0;i<amount;i++){
            HT[i].Lchild=-1;
            HT[i].parent=-1;
            HT[i].Rchild=-1;
            HT[i].weight=*wet;
            wet++;
        }
        for(i;i<total;i++){
            HT[i].Lchild=-1;
            HT[i].Rchild=-1;
            HT[i].parent=-1;
            HT[i].weight=0;
        }
    
        int min1=0,min2=0;
        /*注意此处i的初始值,要对这个过程加以理解,霍夫曼树是用amount之后的分量来存储的,故不能写i=0*/ 
        for(i=amount;i<total;i++){
            SelectMin(HT,min1,min2,i);
            HT[min1].parent=i;
            HT[min2].parent=i;
            HT[i].Lchild=min1;
            HT[i].Rchild=min2;
            HT[i].weight=HT[min1].weight+HT[min2].weight;/*注意新生成的节点的权值为选出的两个最小的节点的权值之和*/ 
        }
        return HT;
    }

    这个问题主要是对建立霍夫曼树的过程理解不够透彻,导致在为HT分配内存时写错大小,和循环过程中将i的初始值误写为0,今后应当注意。

    问题三:出现在HuffmanCoding函数中

    Status HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int amount){
        int i=0;
        /*要先给HC分配内存。HC存储了amount个指向霍夫曼码的指针*/ 
        HC=(HuffmanCode)malloc(amount*sizeof(char *));
        if(!HC)
          return ERROR;
        char * code;
        code=(char *)malloc(amount*sizeof(char));
        if(!code)
           return ERROR;
        code[amount-1]='\0';
        for(i=0;i<amount;i++){
            int current=i;
            int start=amount-1;
            int father=HT[i].parent;
            while(father!=-1){
                if(current==HT[father].Lchild)
                    code[--start]='0';
                else
                    code[--start]='1';
                current=father;
                father=HT[father].parent;
            }
            /*HC[i]是HC中若干个存储单元之一,存储着一个具体字符的霍夫曼码,所以分配内存空间时sizeof()中为char*/ 
            HC[i]=(char *)malloc((amount-start)*sizeof(char));
            if(!HC[i])
               return ERROR;
            strcpy(HC[i],code+start); 
        }
        free(code);
        code=NULL;
    }

    对HC的用途理解不够到位,再次强调,HC是一个存储了若干个指向霍夫曼码的指针的数组,HC[i]则用于存储具体字符的霍夫曼码

    问题四:反复出现在主函数之中,必须加以记录,认真反省

    int main(void){
        HuffmanTree HT;
        int amount=0;
        printf("请输入需要编码的字符个数");
        scanf("%d",&amount);
        int i=0;
        int * wet=(int *)malloc(amount*sizeof(int));
        printf("请输入每个字符的权重");
        for(i=0;i<amount;i++){
            scanf("%d",wet+i);
        }
        /*此处忘记写HT=,导致未能成功建立霍夫曼树,由于这里要改变函数形参的值,一般情况考虑传入指针变量,但这个函数如果写成指针又太复杂,
        很容易出错,故这里使用return把建立好的霍夫曼树直接返回,会方便许多,但是切记要把返回值赋给HT!!!*/ 
        HT=CreateHuffmanTree(HT,wet,amount);
        HuffmanCode HC;
        HuffmanCoding(HT,HC,amount);
        for(i=0;i<amount;i++){
            puts(HC[i]);
        }
        free(wet);
    } 
    展开全文
  • 如何快速画出霍夫曼树

    千次阅读 多人点赞 2018-07-01 21:24:13
    哈夫曼树(霍夫曼树)又称为最优二叉树. 一般用来减少程序整体运行时间,将权重大的放在前面。下面我们以【5、8、4、11、9、13】为例来画出哈夫曼树(数字大小代码权重大小,越大的权重越大)方法/步骤第一步:按...

    哈夫曼树(霍夫曼树)又称为最优二叉树.

     一般用来减少程序整体运行时间,将权重大的放在前面。

    下面我们以【5、8、4、11、9、13】为例来画出哈夫曼树(数字大小代码权重大小,越大的权重越大)

    方法/步骤

    1. 第一步:按从小到大排序。

      【5、8、4、11、9、13】→【4、5、8、9、11、13】

      快速画出哈夫曼树/霍夫曼树/最优树

    2. 第二步:选最小两个数画出一个树,最小数为4和5。

      给定的4、5、8、9、11、13为白色, 红色的9为4+5,与给定的白9无关,新序列为:【红9(含子节点4、5)、8、9、11、13】

      快速画出哈夫曼树/霍夫曼树/最优树

    3. 3

      之后一直重复第一、第二步:排序然后取两个最小值。实际就是一个递归过程

         排序:

      快速画出哈夫曼树/霍夫曼树/最优树

    4. 4

      取两个最小数8和9:

      快速画出哈夫曼树/霍夫曼树/最优树
    5. 5

      排序:

      快速画出哈夫曼树/霍夫曼树/最优树
    6. 6

      取两个最小数9和11:

      快速画出哈夫曼树/霍夫曼树/最优树
    7. 7

      排序,然后取两个最小数13和17:

      快速画出哈夫曼树/霍夫曼树/最优树
    8. 8

      取两个最小数20和30:

      快速画出哈夫曼树/霍夫曼树/最优树

    展开全文
  • 霍夫曼树二、构建步骤三、代码实现 一、相关概念 1.节点的路径及路径长度 路径:在树中,一个节点向下到达另一个节点的通路,称为路径。 路径长度:路径中经历的分支数。 图中节点1到节点4的路径就是:1->2,2-&...
  • python实现霍夫曼树以及编码

    千次阅读 2018-11-29 16:49:08
    python实现霍夫曼树以及编码 再看移动通信的时候了解到了霍夫曼(Huffman)编码,花了一些时间进行了霍夫曼编码的python实现。文章内容包括霍夫曼树的生成,以及相应编码的生成,每一部分都会有完整的代码,个人...
  • 什么是霍夫曼树 霍夫曼树是二叉树的一种特殊形式,又称为最优二叉树,其主要作用在于数据压缩和编码长度的优化。 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树...
  • 文章目录最优树的定义如何构造最优树(霍夫曼算法)霍夫曼编码前缀编码总结 最优树的定义 节点的路径长度定义为:从根节点到该节点的路径上分支的数目。 的路径长度定义为:中每个节点的路径长度之和。 的带权...
  • 哈夫曼原理,及构造方法

    万次阅读 多人点赞 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 一. 目的: 找出存放一串字符所需的最少的二进制编码 二. 构造方法: 首先统计出每...
  • 哈夫曼

    万次阅读 多人点赞 2017-12-29 20:53:34
    什么是哈夫曼? 让我们先举一个例子。 判定:  在很多问题的处理过程中,需要进行大量的条件判断,这些判断结构的设计直接影响着程序的执行效率。例如,编制一个程序,将百分制转换成五个等级输出。...
  • 霍夫曼树和霍夫曼编码原理

    万次阅读 2016-04-10 20:20:59
    一、哈夫曼的概念和定义   什么是哈夫曼? 让我们先举一个例子。 判定:  在很多问题的处理过程中,需要进行大量的条件判断,这些判断结构的设计直接影响着程序的执行效率。例如,编制一个程序,将百分...
  • 霍夫曼树也称为称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度 霍夫曼编码,又译为哈夫曼编码、赫夫曼编码,。是一种用于无损数据压缩...
  • 哈夫曼树霍夫曼树)又称为最优树. 1、路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的...
  • 哈夫曼树 定义: 设二叉树具有n个带权值的叶节点,那么从根节点到各个叶节点的路径长度与相应节点权值的乘积的和,叫做二叉树的带权路径长度。 下图WPL(带权路径长度)的计算: WPL = 2*2+2*3+1*1 = 11 ....
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 什么是哈夫曼树呢? 哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。下面用一幅图来说明。 它们的带权路径长度分别为: 图a: WPL=5*2+7*2+2*2+13*2=54 图b: WPL=5*3+2*3+7*2+13*1=48 可见,图...
  • 哈夫曼树以及哈夫曼编码的构造步骤

    万次阅读 多人点赞 2018-06-11 20:49:05
    注意:哈夫曼树并不唯一,但带权路径长度一定是相同的。(1)8个结点的权值大小如下:(2)从19,21,2,3,6,7,10,32中选择两个权小结点。选中2,3。同时算出这两个结点的和5。(3)从19,21,6,7,10,32,5中...
  • 哈夫曼树C++实现

    千次阅读 2015-11-30 17:08:34
    Huffman Tree,中文名是哈夫曼树霍夫曼树,它是最优二叉树。 定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若树的带权路径长度达到最小,则这棵树被称为哈夫曼树。 这个定义里面涉及到了几个陌生的概念,...
  • 数据结构(15)--哈夫曼树以及哈夫曼编码的实现

    万次阅读 多人点赞 2016-03-01 17:28:40
    参考书籍:数据结构(C语言版)严蔚敏... 假设有n个权值{w1, w2, ..., wn},试构造一棵含有n个叶子结点的二叉树,每个叶子节点带权威wi,则其中带权路径长度WPL最小的二叉树叫做最优二叉树或者哈夫曼树。 特点:哈...
  • 哈夫曼树及python实现

    万次阅读 2017-12-26 21:45:31
    最近在看《tensorflow实战》中关于RNN一节,里面关于word2vec中涉及到了哈夫曼树,因此在查看了很多博客(文末)介绍后,按自己的理解对概念进行了整理(拼凑了下TXT..),最后自己用python实现Haffuman树的构建及...
  • 哈夫曼树及哈夫曼编码详解【完整版代码】

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

    千次阅读 2015-01-13 13:24:00
    Huffman Tree,中文名是哈夫曼树霍夫曼树,它是最优二叉树。 定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若树的带权路径长度达到最小,则这棵树被称为哈夫曼树。 这个定义里面涉及到了几个陌生的概念,...
  • 哈夫曼树的基本构建与操作

    万次阅读 多人点赞 2016-11-29 20:02:32
    看到的讲解huffman的一篇比较好懂的博客,唯一不足的地方就是代码里面使用Malloc时没有强制类型转换。。。。 出处:http://blog.csdn.net/wtfmonking/article/details/17150499# 1、基本概念 a、路径和路径长度 ...
  • 如何根据概率求哈夫曼树如何根据概率求哈夫曼树如何根据概率求哈夫曼树如何根据概率求哈夫曼树
  • 哈夫曼树详解

    千次阅读 2016-12-05 20:23:55
    二叉树中有一种特别的树——哈夫曼树(最优二叉树),其通过某种规则(权值)来构造出一哈夫曼二叉树,在这个二叉树中,只有叶子节点才是有效的数据节点(很重要),其他的非叶子节点是为了构造出哈夫曼而引入的!...
  • 数据结构 - 哈夫曼树 - 哈希树 - 字典树 - 面试中可能会涉及的树知识点 数据结构是面试中必定考查的知识点,面试者需要掌握几种经典的数据结构:线性表(数组、链表)、栈与队列、树(二叉树、二叉查找树、平衡...
  • 原理:哈夫曼树是一种单词树,广泛使用于数据压缩之中。将会根据每个字符的权重,来构建一颗Huffman树,同时根据Huffman树对原来的文本进行二次编码,以达到压缩数据的目的。比如当我们对AAABBBA进行Huffman树压缩时...
  • 哈夫曼树的Java构造

    2019-01-11 10:43:40
    Java哈夫曼编码实验–哈夫曼树的建立,编码与解码 建树,造树,编码,解码 一、哈夫曼树编码介绍 1、哈夫曼树: (1)定义:假设有n个权值{w1, w2, …, wn},试构造一棵含有n个叶子结点的二叉树,每个叶子节点...
  • 哈夫曼树 C语言实现

    万次阅读 多人点赞 2014-01-12 12:01:16
    哈夫曼树 C语言实现 分类: Data structure & Algorithm2013-12-06 23:10 180人阅读 评论(0) 收藏 举报 哈夫曼树哈夫曼编码 目录(?)[+] 1、基本概念 a、路径和路径长度 若在一棵树中存在着一个...
  • C/C++ 哈夫曼树的构造、编码以及译码

    万次阅读 多人点赞 2017-01-05 15:10:34
    题目:假设用于通信的...要求:画出哈夫曼树哈夫曼树的构造 哈夫曼编码及译码的实现 我从课本上面摘抄了一个题目,题目大概是上面这样的,我们这里只是详细的说明一下哈弗曼树要怎么构建。借用一下这个题目。哈夫曼

空空如也

1 2 3 4 5 ... 20
收藏数 22,652
精华内容 9,060
关键字:

霍夫曼树