精华内容
下载资源
问答
  • 主要为大家详细介绍了C语言实现哈夫曼树构建,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 哈夫曼树构建

    2021-01-08 03:14:38
    哈弗曼树构建过程 将带权值的节点进行排序,形成有序的链表。 取出链表头两个节点,权值相加形成新节点,并加入上述链表中重新排序,两节点分别为构建为左右子树,新创建的节点为父节点。 重复步骤2直到链表节点为...
  • 本文以实例形式讲述了C++实现哈夫曼树简单创建与遍历的方法,比较经典的C++算法。 本例实现的功能为:给定n个带权的节点,如何构造一棵n个带有给定权值的叶节点的二叉树,使其带全路径长度WPL最小。 据此构造出最...
  • 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成 本。...将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。
  • 实验题:构造哈夫曼树生成哈夫曼编码 编写一个程序,构造一棵哈夫曼树,输出对应的哈夫曼编码和平均查找长度,并对下表(所示的数据进行验证。 单词及出现的频度 单词: The of a to and in that he is at on for ...

    实验题:构造哈夫曼树生成哈夫曼编码
    编写一个程序,构造一棵哈夫曼树,输出对应的哈夫曼编码和平均查找长度,并对下表(所示的数据进行验证。

    单词及出现的频度
    单词: The of a to and in that he is at on for His are be
    频度 :1192 677 541 518 462 450 242 195 190 181 174 157 138 124 123

    #include <iostream>
    #define N 50
    #define M 2*N-1
    using namespace std;
    //哈夫曼树结点定义
    typedef struct
    {
        string data;
        double weight;
        int parent;
        int lchild;
        int rchild;
    }HTNode;
    //哈夫曼编码结点定义
    typedef struct
    {
        char cd[N];
        int start;
    }HCode;
    //创建哈夫曼树
    void CreateHT(HTNode ht[], int n)
    {
        int i, k, lnode, rnode;
        double min1, min2;//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 = INT_MAX;
            lnode = rnode = -1;//记录可用的最小的两个结点的位置
            for (k = 0; k <= i - 1; k++)//随着过程的进行,会加入两个选用结点构成的新结点,所以判断条件为k<=i-1
            {
                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[i].weight = ht[lnode].weight + ht[rnode].weight;//产生新节点
            ht[i].lchild = lnode; ht[i].rchild = rnode;//记录新节点的孩子结点
            ht[lnode].parent = i; ht[rnode].parent = i;//记录孩子结点的父亲
        }
    }
    //求哈夫曼编码
    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;//从该节点倒着回到根结点,编码长度最大也不会超过n
            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;
        }
    }
    //输出哈夫曼编码并求其平均查找长度
    void DispHCode(HTNode ht[], HCode hcd[], int n)
    {
        int i, k;
        int sum = 0, m = 0, j;//sum存储树的带权路径长度,m存储权和,j存储路径长度
        cout << "输出哈夫曼编码:" << endl; //输出哈夫曼编码
        for (i = 0; i < n; i++)
        {
            j = 0;
            cout << ht[i].data << '\t';
            for (k = hcd[i].start; k <= n; k++)//输出哈夫曼编码
            {
                cout << hcd[i].cd[k];
                j++;//路径长度+1
            }
            m += ht[i].weight;
            sum += ht[i].weight * j;
            cout << endl;
        }
        cout << "平均长度=";
        cout << 1.0 * sum / m;
    }
    int main()
    {
        int n = 15, i;
        string str[] = { "The","of","a","to","and","in","that","he","is","at","on","for","His","are","be" };
        int fnum[] = { 1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123 };
        HTNode ht[M];
        HCode hcd[N];
        for (i = 0; i < n; i++)
        {
            ht[i].data = str[i];
            ht[i].weight = fnum[i];
        }
        CreateHT(ht, n);//创建哈夫曼树
        CreateHCode(ht, hcd, n);//求得哈夫曼编码
        DispHCode(ht, hcd, n);//输出哈夫曼编码和平均查找长度
        return 0;
    }
    

    运行结果:
    在这里插入图片描述
    如果本文对你有帮助的话,请👍哦(●ˇ∀ˇ●)

    展开全文
  • 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。...本资源通过传入数组的方式构建哈夫曼树,并实现构建哈夫曼树的遍历
  • 哈夫曼树构建

    2020-08-24 22:09:56
    哈夫曼树构建 1.定义 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点...

    哈夫曼树的构建

    1.定义

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

    2.构造

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

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

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

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

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

    3代码实现

    public class HuffManTree {
    
    
        public static void createHuffmanTree(int[] arr) {
            //方便排序先将数组转成ArrayList
            List<Node> nodes = new ArrayList<Node>();
            for (int i : arr) {
                nodes.add(new Node(i));
            }
            
            /*
                循环将最小的两 个数组成新的二叉树
                然后将最小的数移除
                将新的二叉树放到数组中
                直达数组中只剩一个数为止
                
             */
            while (nodes.size() > 1) {
                //排序
                Collections.sort(nodes, new NodeComparator());
                //取出最小的两位将其组合一个新的二叉树
                Node leftNode = nodes.get(0);
                Node rightNode = nodes.get(1);
                Node parent = new Node(leftNode.getValue() + rightNode.getValue());
                parent.setLeft(leftNode);
                parent.setRight(rightNode);
                //将其从数组中移除
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                //把新的节点放入数组中。
                nodes.add(parent);
            }
    
    
        }
    
    }
    
    class Node {
        private int value;
        private Node left;
        private Node right;
        
        public Node(int value) {
            this.value = value;
        }
    
        public int getValue() {
            return value;
        }
    
        public void setValue(int value) {
            this.value = value;
        }
    
        public Node getLeft() {
            return left;
        }
    
        public void setLeft(Node left) {
            this.left = left;
        }
    
        public Node getRight() {
            return right;
        }
    
        public void setRight(Node right) {
            this.right = right;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
        
    }
    //实现比较接口
    class NodeComparator implements Comparator<Node> {
    
        @Override
        public int compare(Node o1, Node o2) {
            return o1.getValue() - o2.getValue();
        }
    }
    
    展开全文
  • 数据结构课程 实验报告 实验名称 哈弗曼编码和译码 专业班级 电子信息科学与技术0904 姓 名 秦杰 学 号 1404090506 指导教师 胡志坤 2011年 11月 实验四哈夫曼编码和译码 实验目的和要求 掌握哈夫曼树的基本概念及其...
  • 哈夫曼树原理,及构造方法

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

    哈夫曼树(最优二叉树)

    百度百科:https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin

    一. 目的:

    找出存放一串字符所需的最少的二进制编码

    二. 构造方法:

    首先统计出每种字符出现的频率!(也可以是概率)//权值

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

               例如:频率表 A:60,    B:45,   C:13   D:69   E:14   F:5  G:3

    第一步:找出字符中最小的两个,小的在左边,大的在右边,组成二叉树。在频率表中删除此次找到的两个数,并加入此次最小两个数的频率和。

    FG最小,因此如图,从字符串频率计数中删除FG,并返回GF的和 8频率表

     重复第一步:

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

    频率表 A:60,    B:45,   C:13   D:69   E:14   FG:8

    最小的是 FG:8C:13,因此如图,并返回FGC的和:21频率表。

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

    重复第一步:

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

    频率表 A:60    B: 45   D: 69   E: 14   FGC: 21

    如图

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

    重复第一步

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

    频率表 A:60    B: 45   D: 69  FGCE: 35

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

    重复第一步

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

    频率表 A:60   D: 69  FGCEB: 80

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

    重复第一步

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

    频率表 AD:129  FGCEB: 80

    添加 0 和 1,规则左0 右1

     

    频率表 A:60,    B:45,   C:13   D:69   E:14   F:5  G:3

    每个 字符 的 二进制编码 为(从根节点 数到对应的叶子节点,路径上的值拼接起来就是叶子节点字母的应该的编码)

    字符编码
    A10
    B01
    C0011
    D11
    E000
    F00101
    G00100

     

     

     

     

     

     

     

     

     

    那么当我想传送 ABC时,编码为 10 01 0011

    思考:

    大家观察 出现得越多的字母,他的编码越短 ,出现频率越少的字母,他的编码越长。

    在信息传输过程中,如果这个字母越多,那么我们希望他越瘦小(编码短)这样占用的编码越少,其实编码长的字母也是让频率比它多的字母把编码短的位子都占用后,他才去占用当前最短的编码。至此让总的编码长度最短。

    且要保证长编码的不与短编码的字母冲突:

    比如 不能出现 读码 读到 01  还有长编码的 字母为011,如果短编码为一个长编码的左起子串,这就是冲突,意思就是说读到当前位置已经能确定是什么字母时不能因为再读取一位或几位让这个编码能表示另外的字母,

    但哈夫曼树(最优二叉树)在构造的时候就避免了这个问题。为什么能避免呢,因为哈夫曼树的它的字母都在叶子节点上,因此不会出现一个字母的编码为另一个字母编码左起子串的情况。

     

    提问:

    1.为什么要保证长编码不与短编码冲突?

    冲突情况:如果我们已经确定D,E,F,G 用 01 ,010 ,10,001的2进制编码来传输了。那么想传送FED时,我需要传送     1001001,接收方可以把它解析为FDG(10 01 001),当然也能解析为FED(10 010 01),他两编码一样的,这就是编码冲突,(这里编码冲突的原因,也是因为编码时,D的编码是E的编码的左起子串了)显然这是不行的,就像我说压脉带,你如果是日本人会理解为 (你懂得),这就是发出同一种语,得出不同的意的情况。所以不能让一个字母的二进制代表数,为另一个字母的二进制代表数的子串。但为什么实际情况只要求编码时,一个编码不是另一编码的左起子串呢而不是绝对意义上的非子串呢,因为计算机从数字串的左边开始读,如果从右边读,那么可以要求是非右起(无奈)。你又可以问了为什么编码要求是非左起非右起不直接规定不能是子串呢(也行,不过=>),比如说原文中B就是C,F,G的子串,那这不就不符合规则了么。这里是为了哈夫曼的根本目的,优化编码位占用问题,如果完全不能有任何子串那么编码将会非常庞大。但这里计算机是一位一位的·读取编码的,只需要保证计算机在读取中不会误判就行。并且编码占用最少。

    code:0110101001110

    左起子串:011

    右起子串:110

    绝对非子串:1110111  此串在code中完全找不到

    2.那么哈夫曼树怎么避免左起子串问题呢?

    因为哈夫曼是从叶子节点开始构造,构造到根节点的,而且构造时,都是计算两个权值的节点的和与其他叶子节点再生成一个父节点来组成一个新的树。并且不允许任何带有权值的节点作为他们的父节点。这也保证了所有带有权值的节点都被构造为了叶子节点。然后最后编码的时候是从根节点开始走到叶子节点而得出的编码。在有权值的节点又不会出现在任何一条路的路途中的情况,只会出现在终点的情况下,因此不会出现01代表一个字母011又代表一个字母。

    又如原文ABC编码为10010011的情况,当计算机读到10时,由于有左起子串不冲突的原则。那么计算机完全可以保证当前的10就是A字母,然后再往下读010011的部分,然后当读到01时,也完全能确定B,C同理,而不用说因为会出现冲突的编码而接着继续读取之后的编码来确定前面的编码。这样对信息的判断和效率是相当的不利的,也不是说不可以。即使你ABCD,分别用01,011,0111,01111来代替也行,传输后也能精确识别,但是数据量极大呢,想代替整个中文编码呢,那0后面得多少个1才能代表完。因此哈夫曼就是为了获得最少编码量代替最多字符串,并且不冲突,系统不会误判而产生的。

    3.这里要提一下同权不同构

    已经有朋友问起这个问题了。这里要说一下哈夫曼树的构造并不是唯一的

    考虑如下情况:

    有权值分别为 5,29,7,8,14,23,3,11的情况,可以如下图一样构造。

    带权路径长度:

    (5+3+7+8)*4+

    (11+14)*3+

    (23+29)*2

    =271

    也可以如下图构造:

    带权路径长度:

    (3+5)*5+

    7*4+

    (8+11+14)*3+

    (23+29)*2

    =271

    这两种不同的方式构造出来的哈夫曼树,得出的带权路径长度相等,那么选哪颗树都可以,这就叫同权不同构

     

    此问题由博主 https://me.csdn.net/weixin_43690959 昵称:叫我Tim就好了~ 提出,在这里对他表示感谢。

     

     

     

    看懂的朋友留个赞,没看懂的留言我给你单独讲 _(:з」∠)_

    展开全文
  • 哈夫曼树建立.cpp

    2020-01-04 17:30:41
    自己码的C语言哈弗曼的建立,代码格式整齐,清晰易懂,能正确运行,包含文件的编码解码和压缩功能,很不错的代码,很容易用其他语言复现
  • C++实现哈夫曼树及哈夫曼编码,代码简介https://blog.csdn.net/qq_41664447/article/details/90736442,C++源程序可直接运行
  • 给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短...使用数组构建哈夫曼树,并可用该树构造哈夫曼编码。
  • 哈夫曼树构建哈夫曼编码的一种方法,构造方式如下: 如有队列 {a, b, c, d, e, f, g} 其权值为 {05, 24, 08, 17, 34, 04,13} 求对应a~g的Huffman编码。     注意一点的是,在构建的时候要把...

    哈夫曼树是构建哈夫曼编码的一种方法,构造方式如下:

    如有队列 {a, b, c, d, e, f, g}

    其权值为 {05, 24, 08, 17, 34, 04,13}

    求对应a~g的Huffman编码。

     

     

    注意一点的是,在构建的时候要把 小的数放左子树,大的放右子树,然后再构建。最后的结构为

    a:0011  (编码长度为4)

    b:01     (编码长度为2)

    c:000   (编码长度为3)

    d:101   (编码长度为3)

    e:11     (编码长度为2)

    f:0010  (编码长度为4)

    g:100   (编码长度为3)

    e:11     (编码长度为2)

    展开全文
  • 文章目录哈夫曼树构建及编码一、什么是哈夫曼树二、什么是哈夫曼编码三、怎么建哈夫曼树、求哈夫曼编码四、为什么哈夫曼编码能实现压缩 声明:关于文件压缩,不是本文的重点,本文只说明并讨论哈夫曼树构建和...
  • 哈夫曼树构建哈夫曼树编码

    万次阅读 2018-09-09 14:56:29
    哈夫曼树构建: 注意:(1).首先把一组数3 5 6 8 9 12 15从小到大排列 (2).选取里面最小2个,顶点出为2个数的和 (3).新产生的顶点在与原先的数字进行比较,在里面选取2个最小的数,重复(2)的步骤 (4...
  • 给一个数列{10,7,8,3,26,5,1},要求转成为一棵哈夫曼树。 分析思路以及图解: 第一步:将数列进行排序,按从小到大的顺序。最终结果为{1,3,5,7,8,10,26},根据每个数值创建结点,组成结点数组 第二步:取出...
  • 介绍 哈夫曼(Haffman)这种方法的基本思想如下: ①由给定的n个权值{W1,W2,…,Wn}构造n棵只有一个...④重复②、③两步,当F中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树。 对于同一组给定叶子结点所构
  • 哈夫曼树构建代码

    2020-12-15 11:40:21
    哈夫曼树构建代码 输入一个字符串,构建相应的哈夫曼树,输出WPL。 #include <iostream> #include<cstdio> #include<cstring> #include<stdlib.h> using namespace std; #define INF 0x3...
  • c++ 构建哈夫曼树

    2020-05-08 18:55:09
    接下来介绍哈夫曼树的构造方法,假设给定n个字符及其对应的频率(出现次数),求出用哈夫曼编码后编码串的长度。 比如: 4 //字符个数 a 1 b 2 c 3 d 4 会返回19。(如果不知道怎么算请看上面链接的博客) c++构造 ...
  • 构建哈夫曼树

    2020-05-12 11:14:17
    一、哈夫曼树也叫赫夫曼树,是一颗权值路径最小的二叉树。 我们用的测试数据是 :{6,32,15,21,3,43,69,52,39,70}; 二、构建完的树如下图: 三、代码实现 ... //构建哈夫曼树的节点 int[] da..
  • 用户键盘输入若干个整数作为待编码字符的权值,程序建立哈夫曼树并输出各字符的哈夫曼编码。
  • 哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径...
  • /********************************************************************** * Description : create huffmanTree and huffmanCode by input string * and decode a 0、1 sequence by huffmanCode ...
  • 如何构造哈夫曼树

    千次阅读 2021-05-15 19:52:58
    什么是哈夫曼树2.哈夫曼树的用处举例3.构造一棵哈夫曼树的思路4.哈夫曼编码实现代码 1.什么是哈夫曼树 设有n个权值{w1,w2,w3,…,wn},构造有n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度最小的...
  • 哈夫曼树构建、编码以及带权路径长计算

    万次阅读 多人点赞 2018-09-17 14:17:58
    给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 构造哈夫曼...
  • 本资源是数据结构中利用最小堆实现哈夫曼树的一个C++代码,仅供参考,欢迎指正
  • 哈夫曼树_123456

    2016-04-19 21:31:41
    哈夫曼树 测试用
  • 哈夫曼树构建(C语言版) 课程要求: 左0,右1 左子树根节点 < 右 子树根节点 节点 data, w , lchild, rchild 建立哈夫曼 (有序单链表) 初始:循环输入字符与权值,创建节点,插入到链表中 形成一个包含n个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,385
精华内容 2,154
关键字:

哈夫曼树构建方法