精华内容
下载资源
问答
  • Python实现霍夫曼树

    2020-12-21 00:45:37
    Python实现霍夫曼树 霍夫曼树是一种特殊的二叉树,是一种带权路径长度最短的二叉树,又称为最优二叉树。 给定 N 个权值作为二叉树的 N 个叶节点的权值,构造一棵二叉树,若该二叉树的带权路径长度达到最小,则称该...
  • 利用最小堆编程实现给定权值集合下构造相应霍夫曼树的算法,并解决以下问题: 有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。 (1)构造对应的编码哈夫曼树(要求左子树根结点的权小于等于右子树根结点...
  • 在一批数中, 选择两个最小的数字,用一个类似于树杈的“树枝”连接上两个最小的数。在顶点处计算出这两个数字的和 并写在上面。然后再比较剩下的数字和这个和的大小,再取出两个最小的数字进行排列
  • 主要介绍了使用C语言详解霍夫曼树数据结构,包括一道AMC相关的例题演示需要的朋友可以参考下
  • NULL 博文链接:https://jacky-dai.iteye.com/blog/2307964
  • 霍夫曼树

    2020-01-03 23:08:22
    霍夫曼树是二叉树的一种特殊形式,又称为最优二叉树,其主要作用在于数据压缩和编码长度的优化。 重要概念 路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支...

    前言

    霍夫曼树是二叉树的一种特殊形式,又称为最优二叉树,其主要作用在于数据压缩和编码长度的优化。

    重要概念

    路径和路径长度

    在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。

    图2.1

    图2.1所示二叉树结点A到结点D的路径长度为2,结点A到达结点C的路径长度为1。

    结点的权及带权路径长度

    若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。
    图2.2展示了一棵带权的二叉树

    图2.2

    树的带权路径长度

    树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。
    图2.2所示二叉树的WPL:
    WPL = 6 * 2 + 3 * 2 + 8 * 2 = 34;

    霍夫曼树

    定义

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

    图3.1

     

    叶子结点为A、B、C、D,对应权值分别为7、5、2、4。
    3.1.a树的WPL = 7 * 2 + 5 * 2 + 2 * 2 + 4 * 2 = 36
    3.1.b树的WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 35
    由ABCD构成叶子结点的二叉树形态有许多种,但是WPL最小的树只有3.1.b所示的形态。则3.1.b树为一棵霍夫曼树。

    构造霍夫曼树

    构造霍夫曼树主要运用于编码,称为霍夫曼编码。现考虑使用3.1中ABCD结点以及对应的权值构成如下长度编码。
    AACBCAADDBBADDAABB。
    编码规则:从根节点出发,向左标记为0,向右标记为1。
    采用上述编码规则,将图3.1编码为图3.2所示:

    图3.2

    构造过程:
    3.1.a所示二叉树称为等长编码,由于共有4个结点,故需要2位编码来表示,编码结果为:

    结点编码
    A00
    B01
    C10
    D11

    则AACBCAADDBBADDAABB对应编码为:
    00 00 10 01 10 00 00 11 11 01 01 00 11 11 00 00 01 01
    长度为36。
    3.1.b构造过程如下:
    1)选择结点权值最小的两个结点构成一棵二叉树如图3.3:

    图3.3

    2)则现在可以看作由T1,A,B构造霍夫曼树,继续执行步骤1。
    选则B和T1构成一棵二叉树如图3.4:

    图3.4

    3)现只有T2和A两个结点,继续执行步骤1。
    选择A和T2构成一棵二叉树如图3.5:

    图3.5

    经过上述步骤则可以构造完一棵霍夫曼树。通过观察可以发现,霍夫曼树中权值越大的结点距离根结点越近。
    按照图3.5霍夫曼树编码结果:

    结点编码
    A0
    B10
    C110
    D111

    则AACBCAADDBBADDAABB对应编码为:
    0 0 110 10 110 0 0 111 111 10 10 0 111 111 0 0 10 10
    编码长度为35。
    由此可见,采用二叉树可以适当降低编码长度,尤其是在编码长度较长,且权值分布不均匀时,采用霍夫曼编码可以大大缩短编码长度。

    代码实现

    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    const int MaxValue = 10000;//初始设定的权值最大值
    const int MaxBit = 4;//初始设定的最大编码位数
    const int MaxN = 10;//初始设定的最大结点个数
    struct HaffNode//哈夫曼树的结点结构
    {
        int weight;//权值
        int flag;//标记
        int parent;//双亲结点下标
        int leftChild;//左孩子下标
        int rightChild;//右孩子下标
    };
    struct Code//存放哈夫曼编码的数据元素结构
    {
        int bit[MaxBit];//数组
        int start;//编码的起始下标
        int weight;//字符的权值
    };
    void Haffman(int weight[], int n, HaffNode haffTree[])
    //建立叶结点个数为n权值为weight的哈夫曼树haffTree
    {
        int j, m1, m2, x1, x2;
        //哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点
        for (int i = 0; i<2 * n - 1; i++)
        {
            if (i<n)
                haffTree[i].weight = weight[i];
            else
                haffTree[i].weight = 0;
            //注意这里没打else那{},故无论是n个叶子节点还是n-1个非叶子节点都会进行下面4步的初始化
            haffTree[i].parent = 0;
            haffTree[i].flag = 0;
            haffTree[i].leftChild = -1;
            haffTree[i].rightChild = -1;
        }
        //构造哈夫曼树haffTree的n-1个非叶结点
        for (int i = 0; i<n - 1; i++)
        {
            m1 = m2 = MaxValue;//Maxvalue=10000;(就是一个相当大的数)
            x1 = x2 = 0;//x1、x2是用来保存最小的两个值在数组对应的下标
     
            for (j = 0; j<n + i; j++)//循环找出所有权重中,最小的二个值--morgan
            {
                if (haffTree[j].weight<m1&&haffTree[j].flag == 0)
                {
                    m2 = m1;
                    x2 = x1;
                    m1 = haffTree[j].weight;
                    x1 = j;
                }
                else if(haffTree[j].weight<m2&&haffTree[j].flag == 0)
                {
                    m2 = haffTree[j].weight;
                    x2 = j;
                }
            }
            //将找出的两棵权值最小的子树合并为一棵子树
            haffTree[x1].parent = n + i;
            haffTree[x2].parent = n + i;
            haffTree[x1].flag = 1;
            haffTree[x2].flag = 1;
            haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
            haffTree[n + i].leftChild = x1;
            haffTree[n + i].rightChild = x2;
        }
    }
    void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])
    //由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode
    {
        Code *cd = new Code;
        int child, parent;
        //求n个叶结点的哈夫曼编码
        for (int i = 0; i<n; i++)
        {
            //cd->start=n-1;//不等长编码的最后一位为n-1,
            cd->start = 0;//,----修改从0开始计数--morgan
            cd->weight = haffTree[i].weight;//取得编码对应权值的字符
            child = i;
            parent = haffTree[child].parent;
            //由叶结点向上直到根结点
            while (parent != 0)
            {
                if (haffTree[parent].leftChild == child)
                    cd->bit[cd->start] = 0;//左孩子结点编码0
                else
                    cd->bit[cd->start] = 1;//右孩子结点编码1
                                          //cd->start--;
                cd->start++;//改成编码自增--morgan
                child = parent;
                parent = haffTree[child].parent;
            }
            //保存叶结点的编码和不等长编码的起始位
            //for(intj=cd->start+1;j<n;j++)
            for (int j = cd->start - 1; j >= 0; j--)//重新修改编码,从根节点开始计数--morgan
                haffCode[i].bit[cd->start - j - 1] = cd->bit[j];
     
            haffCode[i].start = cd->start;
            haffCode[i].weight = cd->weight;//保存编码对应的权值
        }
    }
    int main()
    {
        int i, j, n = 4, m = 0;
        int weight[] = { 2,4,5,7 };
        HaffNode*myHaffTree = new HaffNode[2 * n - 1];
        Code*myHaffCode = new Code[n];
        if (n>MaxN)
        {
            cout << "定义的n越界,修改MaxN!" << endl;
            exit(0);
        }
        Haffman(weight, n, myHaffTree);
        HaffmanCode(myHaffTree, n, myHaffCode);
        //输出每个叶结点的哈夫曼编码
        for (i = 0; i<n; i++)
        {
            cout << "Weight=" << myHaffCode[i].weight << "  Code=";
            //for(j=myHaffCode[i].start+1;j<n;j++)
            for (j = 0; j<myHaffCode[i].start; j++)
                cout << myHaffCode[i].bit[j];
            m = m + myHaffCode[i].weight*myHaffCode[i].start;
            cout << endl;
        }
        cout << "huffman's WPL is:";
        cout << m;
        cout << endl;
        return 0;
    }

    结语

    本文主要介绍了霍夫曼树的实际意义和如何构造一棵二叉树。学习霍夫曼树主要是掌握霍夫曼树的构造思想以及构造过程,至于代码实现则是次要的,而且霍夫曼编码实现过程中运用到了贪心算法。

    展开全文
  • 利用最小堆编程实现给定权值集合下构造相应霍夫曼树的算法,并解决以下问题: 有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。 (1)构造对应的编码哈夫曼树(要求左子树根结点的权小于等于右子树根结点...
  • 霍夫曼树 用C ++编写的霍夫曼树。 对于BUPT 2021数据结构和算法分析入门课程。 统计数据
  • 霍夫曼树基本概念: 路径:从一个结点往下到孩子或孙子结点之间的同理 路径长度:如结点1到结点7的路径长度=2 结点的权:将结点的某一属性值作为结点的权 带权路径长度:从根节点到该结点*该结点的权;如...

    霍夫曼树基本概念:

     

    路径:从一个结点往下到孩子或孙子结点之间的同理

    路径长度:如结点1到结点7的路径长度=2

    结点的权:将结点的某一属性值作为结点的权

    带权路径长度:从根节点到该结点*该结点的权;如结点1到结点7的带权路径长度:7*2=14

    的带权路径长度(WPL):该树的所有叶子结点的带权路径长度之和

    霍夫曼树:给定n个权值,构造一颗二叉树并由这n个权值作为数的叶子结点,且该树的带权路径长度(WPL)达最小,这样的二叉树成为最优二叉树,也叫霍夫曼树

    霍夫曼树特点:权值越大的叶子结点离根节点越近

     

     霍夫曼编码:

    编码规则:

    (1)给定一个字符串,统计各个字符出现的次数,将次数作为权值构成霍夫曼树;例如“i like like like java do you like a java”转化为霍夫曼树为:

     

    (2)规定路径向左为0,向右为1,则各个权值的路径即为他们的霍夫曼编码 

     注意:

    (1)霍夫曼编码为前缀编码,即任何编码不会是其他编码的前缀(因为叶子结点)

     (2)若出现权值相同的结点,则根据排序方法不同,对应的霍夫曼编码也不完全相同,但压缩率是相同的。

    代码实现:

    以“i like like like java do you like a java”为例

    结点

    class ByteNode implements Comparable<ByteNode> {
        Byte data;//存放字符本身,注意用包装类方便存入集合中
        int weight;//权值,表示字符出现的次数
        ByteNode left;
        ByteNode right;
    
        public ByteNode(Byte data, int weight) {
            this.data = data;
            this.weight = weight;
        }
    
        @Override
        public int compareTo(ByteNode o) {
            return this.weight - o.weight;
        }
    
        @Override
        public String toString() {
            return "ByteNode{" +
                    "data=" + data +
                    ", weight=" + weight +
                    '}';
        }
    
        //前序遍历
        public void preOrder() {
            System.out.println(this);
            if (this.left != null)
                this.left.preOrder();
            if (this.right != null)
                this.right.preOrder();
        }
    }

     字符串->生成结点并放入List中

     private static List<ByteNode> getList(String str) {
            byte[] bytes=str.getBytes();//转换为byte数组,得到一个个字符
            HashMap<Byte, Integer> counts = new HashMap<>();//统计字符+次数,需要Map实现
            //遍历bytes,统计每个byte出现的次数,存放到Hashmap中
            for (byte b : bytes) {
                Integer count = counts.get(b);//get(key),返回value
                if (count == null)
                    counts.put(b, 1);
                else
                    counts.put(b, count + 1);//如果放入相同的key,则新的值会替换旧的
            }
            //将Map保存的字符+次数生成结点,并存放到List<ByteNode>中
            ArrayList<ByteNode> nodesList = new ArrayList<>();
            for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {//遍历map,将node结点加入到list中
                nodesList.add(new ByteNode(entry.getKey(), entry.getValue()));
            }
            return nodesList;
        }

     输出:

     List->霍夫曼树

    //list生成霍夫曼树
        private static ByteNode getHuffManTree(List<ByteNode> list) {
            while (list.size() > 1) {
                Collections.sort(list);
                ByteNode leftNode = list.get(0);
                ByteNode rightNode = list.get(1);
                ByteNode parent = new ByteNode(null, leftNode.weight + rightNode.weight);//注意父节点都设为null
                parent.left = leftNode;
                parent.right = rightNode;
                list.remove(leftNode);
                list.remove(rightNode);
                list.add(parent);
            }
            return list.get(0);
        }

    返回的为Root结点,非叶子节点的Byte属性都为null,叶子结点的Byte属性不为null

    霍夫曼树->霍夫曼编码表,将表存在Map中

        //由霍夫曼树得到霍夫曼编码表
        static Map<Byte, String> huffmanCodes = new HashMap();//存放编码
        static StringBuilder stringBuilder = new StringBuilder();//初始为null
        /**
         * @param node          传入root结点
         * @param code          路径:左子结点=0;右子结点=1
         * @param stringBuilder 用于拼接路径
         */
        private static void getCodes(ByteNode node, String code, StringBuilder stringBuilder) {
            StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);//每次调用getCodes方法都要new一个StringBuilder,否则回溯时StringBuilder的值并不会回溯
            stringBuilder1.append(code);
            if (node != null) {
                if (node.data == null) {//非叶子结点
                    getCodes(node.left, "0", stringBuilder1);//向左递归
                    getCodes(node.right, "1", stringBuilder1);//向右递归
                } else//到达叶子结点
                    huffmanCodes.put(node.data, stringBuilder1.toString());
            }
        }

    输出:Map<Byte, String>

     字符串->根据霍夫曼编码进行压缩,存放到byte[]数组

    //数据压缩:将一个字符串利用霍夫曼编码压缩后存入byte[]数组
        public static byte[] zip(String str) {
            //获得霍夫曼编码表
            List<ByteNode> list = getList(str);
            ByteNode root = getHuffManTree(list);
            getCodes(root, "", new StringBuilder());
            //将编码表按原字符串的顺序放入StringBuilder中
            byte[] bytes = str.getBytes();
            StringBuilder stringBuilder = new StringBuilder();
            for (byte b : bytes)
                stringBuilder.append(huffmanCodes.get(b));
            //再存放在Byte[]数组中,每个元素存8位
            int len;//返回的byte数组的长度 等价于len=(stringBuilder.length()+7)/8
            if (stringBuilder.length() % 8 == 0)
                len = stringBuilder.length() / 8;
            else
                len = stringBuilder.length() / 8 + 1;
            byte[] by = new byte[len];
            int index = 0;
            for (int i = 0; i < stringBuilder.length(); i += 8) {
                String strByte;
                if (i + 8 > stringBuilder.length()) {//最后不足8位
                    strByte = stringBuilder.substring(i);//截取从第i位开始,一直到结束的字符串
                } else {
                    strByte = stringBuilder.substring(i, i + 8);
                }
                //8位二进制会被识别为补码,将转换为原码,再转为10进制保存在by[]数组中
                by[index] = (byte) Integer.parseInt(strByte, 2);
                index++;
            }
            return by;
        }

    8位霍夫曼编码对应存储在byte[ ]数组中:

    10101000原码是:11010110,转为10进制为-88

     对压缩后的数组解压:

    (1)先写一个方法,能将byte转为二进制字符串

    //数据解压(1):将存储霍夫曼编码的byte数组中每个值转为原字符串
        //flag:判断是否是byte数组的最后一个值,因为最后一个值对应的霍夫曼编码可能不足8位
        private static String byteToBitString(boolean flag, byte b) {
            int temp = b;
            if (flag) {
                temp |= 256;//当b为正数,原码=补码,但结果可能不足8位->将其转为二进制,再与1 0000 0000求或进行位数扩充,取后八位仍是b的原码
            }
            String str = Integer.toBinaryString(temp);//b转换为二进制,再转为其补码保存在s里;由于String存储的字节数更大,只需要s的后8位
            if (flag) {
                return str.substring(str.length() - 8);//从str.length()-8开始,至字符串结束,共8位
            }
            else return str;//若byte数组最后一个值为正,其对应的霍夫曼编码可能8位也可能不足8位,直接返回即可;为负,其对应的霍夫曼编码仍为8位
        }

     

     (2)对压缩后的byte[ ]数组进行解压

    //数据解压(2)
        //by[] 是原字符串经霍夫曼编码后的数组
        private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] by){
            StringBuilder stringBuilder = new StringBuilder();//存放二进制字符串
            //将byte数组转为二进制的字符串
            for (int i=0;i<by.length;i++){
                boolean flag=(i!=by.length-1);//当在by数组最后一个值时,flag=false
                String s = byteToBitString(flag, by[i]);
                stringBuilder.append(s);
            }
            //把字符串按照霍夫曼编码进行解码
            //将原编码表进行反向,方便获取编码对应的字符
            Map<String,Byte> map=new HashMap();
            for (Map.Entry<Byte,String> entry:huffmanCodes.entrySet()){
                map.put(entry.getValue(),entry.getKey());
            }
            List<Byte> list=new ArrayList();//截取的字符存放到List中
            //开始截取
            for (int i=0;i<stringBuilder.length();){
                int count=1;
                boolean flag=true;
                Byte b=null;
                //截取字符串,直至与map中的String能够匹配
                while (flag){
                    String key =stringBuilder.substring(i,i+count);
                    b=map.get(key);
                    if (b==null)//没匹配上
                        count++;
                    else//匹配上了
                        flag=false;
                }
                list.add(b);
                i+=count;
            }
            //List中的字符放入byte[]
            byte[] b=new byte[list.size()];
            for (int i=0;i<list.size();i++){
                b[i]=list.get(i);
            }
            return b;
        }

     将一个文件进行压缩:

    //将一个文件进行压缩
        public static void zipFile(String srcFile, String dstFile) throws Exception {
            FileInputStream fis = new FileInputStream(srcFile);
            byte[] b = new byte[fis.available()];//fis.available()返回文件的大小
            fis.read(b);//文件的内容写入byte数组中
            fis.close();
            byte[] zip = zip(new String(b));
            FileOutputStream fos = new FileOutputStream(dstFile);
            ObjectOutputStream oos = new ObjectOutputStream(fos);
            //利用对象流,写入霍夫曼编码,有利于恢复原文件
            oos.writeObject(zip);
            oos.writeObject(huffmanCodes);
            oos.close();
            fos.close();
        }

    将一个文件进行解压: 

    //将文件进行解压
        public static void decodeFile(String zipFile, String dstFile) throws Exception {
            FileInputStream fis = new FileInputStream(zipFile);
            //用对象输入流得到输入的文件
            ObjectInputStream ois = new ObjectInputStream(fis);
            byte[] by = (byte[]) ois.readObject();
            Map<Byte, String> map = (Map<Byte, String>) ois.readObject();
            //解码
            byte[] decode = decode(map, by);
            //将数据写入文件
            FileOutputStream fos = new FileOutputStream(dstFile);
            fos.write(decode);
            fos.close();
            ois.close();
            fis.close();
        }

    注意点:

    (1)输出字符类型,byte型与int型比较

    byte b = 'a';

    sout(b)-> 97

    byte b1 = 40;

    sout(b1) -> 40

    int i = 97;

    int i1 = 40;

    sout(i == b) -> true

    sout(i1 == b1) -> true 

    (2)String与byte关系,以及相互转换

    String=byte[8],1个byte字节能存8位无符号数字

    byte[ ] b = {'a','b'};

    sout(b); -> [b@41628346

    sout(Arrays.toString(b)); -> [97,98]

    sout(new String(b)); -> ab 

    String转为byte[ ]数组:

    String str ="I like java";

    byte[ ] by = str.getBytes();

    (3)String拼接使用StringBuilder

    StringBuilder线程不安全,StringBuffer线程安全,一般用前者;

    拼接方法一:

    String s = "hello" 会在常量池开辟一个内存空间来存储”hello"。

    s += "world"会先在常量池开辟一个内存空间来存储“world"。然后再开辟一个内存空间来存储”helloworld“。

    这么以来,001与002就成为了垃圾内存空间了。这么简单的一个操作就产生了两个垃圾内存空间,如果有大量的字符串拼接,将会造成极大的浪费。

    拼接方法二:

    StringBuilder的字符串拼接是直接在原来的内存空间操作的,即直接在hello这个内存空间把hello拼接为helloworld。

    StringBuilder s1 = new StringBuilder("hello");

    s1.append("world");

    sout(s1) ->"helloword"

    转为String:

    s1.toString();

    展开全文
  • 霍夫曼树也称为称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度 霍夫曼编码,又译为哈夫曼编码、赫夫曼编码,。是一种用于无损数据压缩...

    零、读前说明

    • 本文中所有设计的代码均通过测试,并且在功能性方面均实现应有的功能。
    • 设计的代码并非全部公开,部分无关紧要代码并没有贴出来。
    • 如果你也对此感兴趣、也想测试源码的话,可以私聊我,非常欢迎一起探讨学习。
    • 由于时间、水平、精力有限,文中难免会出现不准确、甚至错误的地方,也很欢迎大佬看见的话批评指正。
    • 嘻嘻。。。。 。。。。。。。。收!

    一、概述

      漂亮国数学家霍夫曼(David Huffman),也称赫夫曼、哈夫曼等。他在1952年发明了霍夫曼编码,所以就将在编码中用到的特殊的二叉树称为霍夫曼树,编码方式称为霍夫曼编码。膜拜!

      在了解之前,我们先来看看从小就被支配的考试的分数,往往因为那么几分经常喜提男女混合双打套餐一份。在我们学习编程不久,也会有这样一个简单的代码来练习手法,每次编写这样的程序都会想到:为什么 60 分才及格呢 ??(͡° ͜ʖ ͡°)

    if(score < 60) printf("不及格\n");
    else if(score < 70) printf("及格\n");
    else if(score < 80) printf("中等\n");
    else if(score < 90) printf("良好\n");
    else printf("优秀\n");
    
    

      程序运行的结果肯定是没有任何问题的,每次运行出正确的结果,心里的自豪感爆棚呀有没有!! ≧◠◡◠≦✌
      

    图1.1 成绩分布示意图

      
       但是现在学习了数据结构与算法之后,我们发现了端倪:通常学生的成绩呈现正态分布,也就是说 70 - 80 分的学生占大多数,而少于 60 分或者多于 90 分毕竟是少数,所以对于 70 - 80 分的这个分支,通常需要判断三次才能到,那么消耗的时间也就也多,那我们就会发现,这个程序运行的效率有问题,强迫症告诉我,搞他!!!

      那么既然这样的话, 我们来进行简单的计算一下,假设成绩的分布的占比为下表所示这样。

    表1.1 分数占比分布表
    分 数0 ~ 5960 ~ 6970 ~ 7980 ~ 8990 ~ 100
    占 比5%15%40%30%10%

      假设有100个学生,那么根据上面的程序总共需要判断的次数为(占比 乘以 判断次数,且注意最后一个 else 不占次数):

    5 * 1 + 15 * 2 + 40 * 3 + 30 * 4 + 10 * 4 = 315 (次)
      

      那么根据上面表格中所显示的比例,将上面的程序的分支简单的修改一下,将出现频繁的分支往前面移动,出现不多的往后面移动,那么可以将上面的图可以修改为下图这样。

    图1.1 修改和的成绩分布示意图

      
      那么有100个学生的话程序总共需要判断的次数为:

    5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 + 10 * 2 = 220 (次)

      
      明显的,判断的次数有明显的提升,那么上面修改后的图示就是霍夫曼树,也称为最优二叉树

    二、霍夫曼树

    2.1、基本说明

      前面已经对霍夫曼树有了最简单的感觉,那么首先说明:

      路劲:从树中一个节点到另一个节点之间的分支构成两个节点之间的路径
      路劲长度:路劲上分支的数目
      带权路劲长度:从该节点到根节点之间的路劲长度与节点上权的乘积
      树的带权路劲长度:树中所有叶子节点的带权路劲长度之和,通常记为 : W P L = ∑ i = 0 n w i l i WPL = \sum_{i=0}^n w_il_i WPL=i=0nwili

      假设有 n n n 个权值 { w 1 w_1 w1 w 2 w_2 w2,…, w n w_n wn} ,试构造一个有 n n n 个叶子节点的二叉树,每个叶子节点的权 w i w_i wi ,则其中带权路劲长度 W P L WPL WPL 最小的二叉树称做最优二叉树霍夫量树

      所以说,上面提到的两种风格的树的形状,其进行 if 判断的次数,即为其对应的 W P L WPL WPL,明显地第二种形状的树其 W P L WPL WPL最小。

    2.2、构建霍夫曼树

      既然霍夫曼树这么好,那么应该怎么构建这个霍夫曼树呢。霍夫曼最早给出了一个带有一般规律的算法,一般称为霍夫曼算法。描述如下:

      1、根据给定的 n n n 个权值{ w 1 w_1 w1 w 2 w_2 w2,…, w n w_n wn} 构成 n n n 个二叉树的集合 F F F ={ T 1 T_1 T1 T 2 T_2 T2,…, T n T_n Tn}, 其中每个二叉树 T,中只有一个带权为 w i w_i wi 的根结点,其左右子树均为空
      2、在 F 中选取两个根结点的权值最小的树作为左右子树构造一个新的二叉树, 置新的二叉树的根结点的权值为其左右子树上根结点的权值之和
      3、在 F 中删除这两个树,同时将新得到的二叉树加入 F
      4、重复 2、3 步骤,直到 F 只含一个树为止,这个树便是霍夫曼树

    (以上摘自《大话数据结构》P145)

      
      看完上面的总觉得可以了,但是大脑却一个劲的说不行,那我们用下面的一组图图来简单的描述一下上面的总结。

      假设有一个五二叉树在 A、B、C、D、E 构成的森林,权值分别为在 5、15、40、30、10 ,用这个创建一个霍夫曼树。

    图2.1 二叉树集合示意图

      
      1、取上面二叉树集合中两个权值最小的叶子节点组成一个新的二叉树,并且将权值最小的节点最为新二叉树(下图中节点 N 1 N_1 N1 )的左孩子。也就是节点 A (权值为 5 )为新节点的左孩子,节点 E (权值为 10 )为新节点的右孩子。新节点的权值则为两个孩子的权值的和10+5 ),如下图所示。

    图2.2 组建新节点示意图

      
      2、用 N 1 N_1 N1 替换节点 A 和节点 E ,为了统一插入,将新节点 N 1 N_1 N1 插入到集合的前面,如下图所示。

    图2.3 二叉树集合分布示意图

      
      3、重复上面步骤2,再在集合中取一个权值最小的节点 B (权值为 15 )与新节点 N 1 N_1 N1 组成新的节点 N 2 N_2 N2 (权值为 15+15 ),如下图所示。

    图2.4 组建新节点示意图

      
      4、将新节点 N 2 N_2 N2 替换节点 N 1 N_1 N1 与节点 B ,此时集合中还存在三个二叉树。分别为 { N 2 N_2 N2、C、D}
      5、重复上面步骤2,再在集合中取一个权值最小的节点 D (权值为 30 )与新节点 N 2 N_2 N2 组成新的节点 N 3 N_3 N3 (权值为 30+30 ),如下图所示。

    图2.5 二叉树组建示意图

      
      6、将新节点 N 3 N_3 N3 替换节点 N 2 N_2 N2 与节点 D,此时集合中还存在两个二叉树。分别为 { N 2 N_2 N2 、C}
      7、重复上面步骤2,再在集合中取一个权值最小的节点 C(权值为 40)与新节点 N 3 N_3 N3 组成新的节点 N 4 N_4 N4 ,因为节点 C 的权值( 40)小于节点 N 3 N_3 N3 的权值( 60 ),所以节点 N 3 N_3 N3 为新节点 N 4 N_4 N4 的右孩子。新节点 N 4 N_4 N4 的权值为 40+60 ,如下图所示。

    图2.6 霍夫曼树示意图

      
      8、此时集合中就剩下一各二叉树 N 4 N_4 N4 了,所以,霍夫曼树的创建完成了。

      此时,可以计算出来此二叉树的 W P L WPL WPL

    40 * 1 + 30 * 2 + 15 * 3 + 10 * 4 + 5 * 4 = 205
      

      显然此时得到的值为 W P L WPL WPL = 205,比之前我们自行做修改的二叉树的还要小,显然此时构造出来的二叉树才是最优的霍夫曼树

    2.3、霍夫曼树的存储结构

      根据上面的描述,如果树的集合中有 n n n 个节点,那么我就需要 2 n − 1 2n-1 2n1 个空间用来保存创建的霍夫曼树中各个节点的信息。也就是需要创建一个数组 huffmanTree[ 2 n − 1 2n-1 2n1]用来保存霍夫曼树,数组的元素的节点结构如下所示。

    图2.7 霍夫曼树存储结构示意图

      其中:
        weight:权值域,保存该节点的权值
        lchild:指针域,节点的左孩子节点在数组中的下标
        rchild:指针域,节点的右孩子节点在数组中的下标
        parent:指针域,节点的双亲节点在数组中的下标

    三、霍夫曼树的应用 — 霍夫曼编码

    3.1、概述

      霍夫曼树的研究是为了当时在进行远距离数据传输的的最优化的问题,并且在现如今庞大的信息面前,数据的压缩显的尤为主要。而霍夫曼编码是首个使用的压缩编码方案。首先我们了解几个简单的概念。

      编  码:给每个对象标记一个二进制位串来表示一组对象,比如ASCII,指令系统等
      定长编码:表示一组对象的二进制位串的长度相等
      变长编码:表示一组对象的二进制位串的长度不相等,可以根据整体出现的频率来调节
      前缀编码:一组编码中任一编码都不是其他任何一个编码的前缀

      前缀编码保证了在解码时不会出现歧义,而霍夫曼编码就是一种前缀编码。

       比如一组字符串 “hello world”,如果采用ASCII进行编码,那么既可以表示为下表这样(包含空格):

    表3.1 字符串的ASCII表示表
    字符串hello(空格)world
    十六进制表示0x680x650x6C0x6C0x6F0x200x770x6F0x720x6C0x64
    二进制表示0110 10000110 01010110 11000110 11000110 11110010 00000111 01110110 11110111 00100110 11000110 0100

       显然,想要保存或者传输这么一个字符串的话,至少需要 12 个字节(字符串的结束符’\0’),也就是需要 12*8bit 来保存或者传输。

       那么既然提到了霍夫曼编码,那么肯定霍夫曼编码可以解决这个占用多、效率低的问题了。

       首先各个字母出现的次数可以理解为其权值,所以上述字符串中各个字母的权值可以表示为下面这样。

    表3.2 字母权值显示表
    字符串helo(空格)wrd
    权 值11321111

       然后根据前面描述的创建霍夫曼树的步骤(点我查看构造霍夫曼树的详情),我们可以创建出来字符串 “hello world” 的最优的霍夫曼树,如下图左边所示。

    在这里插入图片描述

    图3.1 霍夫曼树示意图

      
       然后在上图左边所示的霍夫曼树中,将左分支上的原本表示权值的数值修改为表示路径的 0 ,将右分支上原本表示权值的数据修改成表示路径的 1,那么现实效果可以如上图右边所示。

    表3.3 字母霍夫曼编码显示表
    字符串hello(空格)world
    霍夫曼编码1111 1101111 11100101101111 10101111 001110

       由此可见,数据的存储或者传输的空间大大的缩小,那么随着字符的增加和多自负权重的不同,这种压缩会更加的显示出其优势。

    3.2、霍夫曼编码的代码实现

       那么根据上面的描述,霍夫曼树、霍夫曼编码的创建的实现代码可以如下编写。

    /**
     *  功  能:
     *      创建一个霍夫曼树
     *  参  数:
     *      weight :保存权值的数组
     *      num    :权值数组的长度,也就是权值的个数 
     *  返回值:
     *      成功 :创建成功的霍夫曼树的首地址
     *      失败 :NULL
     **/
    huffmanTree *Create_huffmanTree(unsigned int *weight, unsigned int num)
    {
        huffmanTree *hTree = NULL;
        if (weight == NULL || num <= 1) // 如果只有一个编码就相当于0
            goto END;
    
        hTree = (huffmanTree *)malloc((2 * num - 1 + 1) * sizeof(htNode)); // 0号下标预留。用来表示初始化的状态,所以要在原来的基础上加1
        if (hTree == NULL)
            goto END;
    
        // 初始化哈夫曼树中的所有结点,均初始化为0
        memset(hTree, 0, (2 * num - 1 + 1) * sizeof(htNode));
        // 将权值赋值成传入的权值,并且从数组的第二个位置开始,i=1
        for (unsigned int i = 1; i <= num; i++)
            (hTree + i)->weight = *(weight + i - 1);
    
        // 构建哈夫曼树,将新创建的节点在原本节点的后边,从num+1开始
        for (unsigned int offset = num + 1; offset < 2 * num; offset++)
        {
            unsigned int index1, index2;
            select_minimum_index(hTree, offset - 1, &index1, &index2); // 获取权值最小的节点的下标
    
            // printf("index1 = %d, index2 = %d, hTree[1] = %d, hTree[2] = %d\n",
            //        index1, index2, hTree[index1].weight, hTree[index2].weight);
    
            (hTree + offset)->weight = (hTree + index1)->weight +
                                       (hTree + index2)->weight; // 将权值最小的两个节点的权值相加醉成新节点的权值
            (hTree + index1)->parent = offset;                   // 权值最小的节点的双亲结点为此新节点
            (hTree + index2)->parent = offset;                   // 值次小的节点的双亲结点为此新节点
            (hTree + offset)->lchild = index1;                   // 此新节点的左孩子为权值最小的节点
            (hTree + offset)->rchild = index2;                   // 此新节点的右孩子为权值次小的节点
        }
    
    END:
        return hTree;
    }
    
    /**
     *  功  能:
     *       查询/计算在特定霍夫曼树下的对应圈权值的霍夫曼编码
     *  参  数:
     *      htree :参考的霍夫曼树
     *      nums  :原本权值的个数
     *      weight:权值
     *  返回值:
     *      成功:返回权值weight对应的编码
     *      失败:NULL
     **/
    huffmanCode *Create_HuffmanCode_One(huffmanTree *htree, unsigned int nums, unsigned int weight)
    {
        huffmanCode *hCode = NULL, *tmpCode = NULL;
        unsigned int i = 0, index = 0, parent = 0;
    
        if (htree == NULL || weight < 1)
            goto END;
    
        // 找到权值匹配的数组的下标
        while (htree[i].weight != weight && i <= nums)
            i++;
        if (i > nums) // 如果成立,额说明没有找到对应的权值,是为假权值
            goto END;
    
        tmpCode = (char *)malloc(sizeof(char) * nums);
        if (tmpCode == NULL)
            goto END;
    
        memset(tmpCode, 0, sizeof(char) * nums);
        // 霍夫曼编码的起始点,一般情况来说,最长的编码的长度为权值个数-1
        index = nums - 1;
        //从叶子到根结点求编码
        parent = (htree + i)->parent;
        while (parent != 0)
        {
            if ((htree + parent)->lchild == (unsigned int)i) //从右到左的顺序编码入数组内
                tmpCode[--index] = '0';                      //左分支标0
            else
                tmpCode[--index] = '1'; //右分支标1
    
            i = parent;
            parent = (htree + parent)->parent; //由双亲节点向霍夫曼树的根节点移动
        }
    
        hCode = (char *)malloc((nums - index) * sizeof(char)); //字符串,需要以'\0'为结束
        if (hCode == NULL)
            goto END;
    
        memset(hCode, 0, (nums - index) * sizeof(char));
        strcpy(hCode, &tmpCode[index]);
    
    END:
        if (tmpCode != NULL)
            free(tmpCode);
        tmpCode = NULL;
    
        return hCode;
    }
    
    /**
     *  功  能:
     *      霍夫曼树的数组权值最小两个节点的下标
     *  参  数:
     *      htree  :输入,霍夫曼树
     *      num    :输入,霍夫曼树数组中有效节点的个数
     *      index1 :输出,权值最小的节点的下标
     *      index2 :输出,权值次小的节点的下标
     *  返回值:
     *      无
     **/
    static void select_minimum_index(huffmanTree *htree, unsigned int num, unsigned int *index1, unsigned int *index2)
    {
        unsigned int i = 1;
        // 记录最小权值所在的下标
        unsigned int indexMin;
        if (htree == NULL || index1 == NULL || index2 == NULL)
            goto END;
    
        // 遍历目前全部节点,找出最前面第一个没有被构建的节点
        while (i <= num && (htree + i)->parent != 0)
            i++;
    
        indexMin = i;
    
        //继续遍历全部结点,找出权值最小的单节点
        while (i <= num)
        {
            // 如果节点没有被构建,并且此节点的的权值比 下标为目前记录的下标的节点的权值小
            if ((htree + i)->parent == 0 && (htree + i)->weight < (htree + indexMin)->weight)
                indexMin = i; // 找到了最小权值的节点,下标为i
            i++;
        }
        *index1 = indexMin; // 最小的节点已经找到了,下标为 indexMin
    
        // 开始查找次小权值的下标
        i = 1;
        while (i <= num)
        {
            // 找出下一个没有被构建的节点,且没有被 index1 指向
            if ((htree + i)->parent == 0 && i != (*index1))
                break;
            i++;
        }
        indexMin = i;
    
        // 继续遍历全部结点,找到权值次小的那一个
        i = 1;
        while (i <= num)
        {
            if ((htree + i)->parent == 0 && i != (*index1))
            {
                // 如果此结点的权值比 indexMin 位置的节点的权值小
                if ((htree + i)->weight < (htree + indexMin)->weight)
                    indexMin = i;
            }
            i++;
        }
        // 次小的节点已经找到了,下标为 indexMin
        *index2 = indexMin;
    
    END:
        return;
    }
    
    

    3.3、测试案例及其运行效果

       测试案例就是主函数实现的代码,主要代码如下。

    #include "../src/huffman/huffman.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main(int argc, const char *argv[])
    {
        int ret = 0;
        char chars[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0'};
        unsigned int weight[] = {5, 7, 2, 4, 1, 9, 8};
        unsigned char length = sizeof(weight) / sizeof(int);
    
        /* 根据已知的权重进行编码,解码 */
        // 创建霍夫曼树
        huffmanTree *htree = fhuffmanTree.buildHTree(weight, length);
        // 打印输出霍夫曼树的关系表格
        fhuffmanTree.printHTree(htree, 2 * length);
        // 创建霍夫曼编码
        huffmanCode **hcode = fhuffmanTree.getHCode(htree, length);
        // 打印输出霍夫曼编码
        fhuffmanTree.printHCode(hcode);
    
        /* 根据已知的字符串进行编码 */
        char *string = (char *)"ADZFBCD";
        char *stringCode = NULL;
        fhuffmanTree.toHcode(hcode, chars, length, string, &stringCode);
        printf("The input string '%s' Encoded by Huffman is : \n\n\t%s\n\n", string, stringCode);
    
        /* 根据已知的字符串进行解码 */
        char *coding = (char *)"110001101110001001";
        char *codeString = NULL;
        fhuffmanTree.toString(htree, chars, length, coding, &codeString);
        printf("The input coding '%s' Decoded by Huffman is : \n\n\t%s\n\n", coding, codeString);
    
        fhuffmanTree.destoryHTree(htree);
        fhuffmanTree.destoryHCode(hcode);
    
        free(stringCode);
        stringCode = NULL;
        free(codeString);
        codeString = NULL;
    
        printf("\nsystem exited with return code %d\n", ret);
    
        return ret;
    }
    
    

       工程管理使用常见的 cmake 进行管理,项目工程结构如下图左上角所示,比较清楚不再赘述。
       项目创建、编译、运行在下图中均已经显示明白,不再赘述。
       具体的测试效果如下图所示。

    图3.2 霍夫曼运行效果示意图

      
      好啦,废话不多说,总结写作不易,如果你喜欢这篇文章或者对你有用,请动动你发财的小手手帮忙点个赞,当然 关注一波 那就更好了,好啦,就到这儿了,么么哒(*  ̄3)(ε ̄ *)。

    上一篇:数据结构(十九) – C语言版 – 树 - 树、森林、二叉树的江湖爱恨情仇、相互转换
    下一篇:数据结构(廿一) – C语言版 – 图 - 图的基本概念

    展开全文
  • 霍夫曼树以及哈夫曼编码 一、什么是哈夫曼树与哈夫曼编码 编码是什么 答: 在ASCII 编码中 ‘a’ = 97 = (01100001)2(01100001)_2(01100001)2​ ‘0’ = 48 = (00110000)2(00110000)_2(00110000)2​ 注意:任何信息...

    霍夫曼树以及哈夫曼编码

    一、什么是哈夫曼树与哈夫曼编码

    1. 编码是什么
      答:
      在ASCII 编码中
      ‘a’ = 97 = ( 01100001 ) 2 (01100001)_2 (01100001)2
      ‘0’ = 48 = ( 00110000 ) 2 (00110000)_2 (00110000)2
      注意:任何信息,在计算机中,都是二进制存储的

    ASCII编码规则下的信息:“aa00” = 0110 0001、01100001、00110000、00110000
    信息的价值在于流通,从一台计算机 传输到 另外一台计算机,传输上面信息,需要传输32个比特位
    假设:计算机的网络带宽是32bit/s, 传上述信息,用时:1s

    在特定场景中:假设需要传输的只有a,b,0,1四种字符需要传输
    重新编排编码a:00, b:01, 0:10, 1:11
    自定义规则下的信息“aa00” = 00 00 10 10
    在带宽不变的情况下,当前只需要传输0.25s
    在相同传输的数据量下,越好的编码方式,传输的效率越快 -> (各个直播平台相同网络下,流畅度的区别)

    1. 定长与变长编码
      1. ASCII 编码和刚刚特定场景下的编码,都属于定长编码
      2. 对于每一种字符,编码长度相同,这就是定长编码
      3. UTF-8编码,是变长编码,UTF-16,是定长编码
      4. 对于每一个字符,编码长度不相同,这就是变长编码
      5. 将定长编码,看成时变长编码的特例
      6. 变长编码,一定不差于定长编码

    变长编码应用场景
    特定场景:

    1. 只有四种字符:ab01
    2. P(a) = 0.8, P(b) = 0.05, P© = 0.1, P(1) = 0.05
      平均编码长度:
      l i l_i li:第i中字符,编码长度
      p i p_i pi:第i中字符,出现概率
      a v g ( l ) = ∑ l i × p i avg(l) = \sum{l_i}\times{p_i} avg(l)=li×pi

    假设,平均编码长度:1.16,估算传输100个字符,需要传输116个比特位
    上述编码的平均编码长度: a v g ( l ) = 2 ∗ ∑ p i = 2 avg(l) = 2 * \sum{p_i} = 2 avg(l)=2pi=2
    新建编码:出现概率大的编码长度短,出现概率小的编码长度长
    新·编码 a : 1 b : 01 0:000 1:001 (问题1:为什么b的编码不能时‘10’)
    平均编码长度: 1 ∗ 0.8 + 2 ∗ 0.05 + 3 ∗ 0.1 + 3 ∗ 0.05 = 1.35 1 * 0.8 + 2 * 0.05 + 3 * 0.1 + 3 * 0.05 = 1.35 10.8+20.05+30.1+30.05=1.35
    意味着,传输100个字符的期望值为135比特位
    优秀的编码都是根据特定场景做的优化

    问题1:为什么b的编码不能是10?
    解码过程,遇到和字典中匹配的字符,立刻解析字符,则当b为10的时候,碰到110,会解析为aa0  b与a冲突
    

    哈夫曼树的建立

    每一次从集合中选出两个概率最低的节点,将他们合并成一棵子树,
    并将新生成的节点,放回到原集合种
    

    哈夫曼编码

    	1. 首先,统计得到每一种字符的概率
    	2. 将n个字符,建立成一棵哈夫曼树
    	3. 每一个字符,都落在叶子节点上
    	4. 按照左0,右1的形式,将编码取出来
    	a : 0.8  b:0.05  0 : 0.1  1 : 0.05
    	***因为所有字符都落在叶子节点上,所以没有任何一个字符时另一个字符的前缀***
    

    在这里插入图片描述

    得到新编码
    a: 0
    0: 10
    b: 110
    c : 111
    哈夫曼编码,平均编码长度:$ 1 * 0.8 + 2 * 0.1 + 3 * 0.05 + 3 * 0.05 = 1.3$

    结论:哈夫曼编码时最优的变长编码 (下述证明)

    二、为什么哈夫曼编码是最优的变长编码(不想了解的可以直接下一步qwq)

    设 P(a) : 0.25 ,P(b) : 0.25 ,P© : 0.25 ,P(d) : 0.25
    则构成的哈夫曼树为:
    在这里插入图片描述
    当P(a) = P(b) = P© = P(d) 时,哈夫曼编码退化为变长编码
    所以,定长编码做的好,哈夫曼编码一定做的好,甚至做的更好

    证明

    证明那个指标最优? 平均编码长度最优, ∑ p i × l i \sum{p_i} \times {l_i} pi×li最小
    当所有字符在叶子节点上

    在这里插入图片描述

    若仅需4个编码,则需在当前的哈夫曼树中选4个节点
    在这里插入图片描述
    越往上的节点,覆盖节点越多,
    越往下的节点,覆盖节点越少。
    对于某个节点覆盖子节点的数量为 2 H − l 2^{H - l} 2Hl

    手写推导
    在这里插入图片描述

    在这里插入图片描述
    熵: − ∑ p i log ⁡ p i -\sum{p_i} \log{p_i} pilogpi 在系统种,最小的平均信息,表示单元的长度(平均编码长度)
    熵越大,系统越复杂

    引出
    交叉熵 − ∑ p i log ⁡ q i -\sum{p_i} \log{q_i} pilogqi
    − ∑ p i log ⁡ q i -\sum{p_i} \log{q_i} pilogqi 越小, p i , q i p_i , q_i pi,qi越相似 , p i = q i p_i = q_i pi=qi时,最小
    − ∑ p i log ⁡ q i -\sum{p_i} \log{q_i} pilogqi 越大, p i , q i p_i, q_i pi,qi相差的越多

    对照推导中
    概率越高( p i p_i pi) L i L_i Li 越大,
    l i ‘ = − l i = log ⁡ L i l_i` = - l_i = \log L_i li=li=logLi − l i -l_i li 越大 l i l_i li越小 则,概率越大,路径长度越小

    推到过程

    1.首先表示平均每编码长度,秋节公式最优解
    2.最终,和熵与交叉熵的关系

    tips:
    这个证明也不是很严谨的,因为哈夫曼编码是离散的,这个证明是连续的

    三、霍夫曼树的代码演示

    #include <stdio.h>
    #include <stdlib.h>
    
    #define swap(a, b) {\
        __typeof(a) __c = a;\
        a = b,b = __c;\
    }
    typedef struct Node {
        char ch;//字符
        double p;//出现的概率
        struct Node *lchild, *rchild;
    } Node ;
    
    Node *getNewNode(char ch, double per) {
        Node *p = (Node *)malloc(sizeof(Node));
        p->ch = ch;
        p->p = per;
        p->lchild = p->rchild = NULL;
        return p;
    }
    
    Node *CombinNode (Node *a, Node *b) {//合并最小的两个节点
        Node *p = getNewNode(0, a->p + b->p);
        p->lchild = a;
        p->rchild = b;
        return p;
    }
    
    void pick_min(Node **arr, int n) {
        for (int j = n - 1; j >= 0; --j) {
            if (arr[n]->p > arr[j]->p) {
            swap(arr[n], arr[j]);
            }
        }
        return ;
    }
    
    Node *getHaffmanTree(Node **arr, int n) {
        for (int i = 1; i < n; i++) {//n个字符,需要合并n - 1次
            pick_min(arr, n - i);//最小的放在n - i处
            pick_min(arr, n - i - 1);//第2小的放在n - i - 1处
            arr[n - i - 1] = CombinNode(arr[n - i], arr[n - i - 1]);
        }//也可以用优先队列简化代码
        return arr[0];//最后剩下的头节点,就是haffman树的根节点
    }
    
    void __output_encode(Node *root, char *str, int k) {//k为层数
        str[k] = 0;
        if (root->lchild == NULL && root->rchild == NULL) {//遇到根节点输出
            printf("%c %s\n", root->ch, str);
            return ;
        }
        str[k] = '0';//左子树为0
        __output_encode(root->lchild, str, k + 1);
        str[k] = '1';//右子树为1
        __output_encode(root->rchild, str, k + 1);
        return ;
    }
    
    void output_encode(Node *root) {
        char str[100];
        __output_encode(root, str, 0);
        return ;
    }
    
    void clear(Node *root) {
        if (root == NULL) return ;
        clear(root->lchild);
        clear(root->rchild);
        free(root);
        return ;
    }
    
    
    int main() {
        int n;
        Node **arr;
        scanf("%d", &n);
        arr = (Node **)malloc(sizeof(Node *) * n);
        for (int i = 0; i < n; i++) {
            char ch[10];
            double p;
            scanf("%s%lf", ch, &p);
            arr[i] = getNewNode(ch[0], p);
        }
        Node *root = getHaffmanTree(arr, n);
        output_encode(root);
        clear(root);
        free(arr);
        return 0;
    }
    

    代码运行结果图
    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • 霍夫曼树(最优二叉树)的实现

    热门讨论 2020-10-20 18:13:41
    霍夫曼树二、构建步骤三、代码实现 一、相关概念 1.节点的路径及路径长度 路径:在树中,一个节点向下到达另一个节点的通路,称为路径。 路径长度:路径中经历的分支数。 图中节点1到节点4的路径就是:1->2,2-&...
  • 霍夫曼树的创建

    2020-07-31 09:25:40
    其实,看过其他人的博客,书籍以及自身理解后,我认为霍夫曼树可以简化代码的储存,让频率高的字段以更短的字符储存,而频率低的字段用更长的字符储存。最终在多次重复中实现简化压缩。(这个别人讲的很清楚了) ...
  • 霍夫曼树与霍夫曼编码(Huffman Tree) 在这样的情况下,如果大多数人都是90分以上,那么大多数人需要进行4次判断才能有结果,造成时间的浪费。 【引申:判断的时候要把最常发生、最可能发生的情况放在前面】 —>...
  • c++霍夫曼树

    2020-11-03 09:26:49
    这个方法是霍夫曼想出来的,称为霍夫曼树 2霍夫曼树的构造 对于文本”BADCADFEED”的传输而言,因为重复出现的只有 ”ABCDEF”这6个字符,因此可以用下面的方式编码: 接收方可以根据每3个bit进行一次字符解码的...
  • 霍夫曼树是二叉树的一种特殊形式,又称为最优二叉树,其主要作用在于数据压缩和编码长度的优化。 2 重要概念 2.1 路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中...
  • 霍夫曼树是二叉树的一种特殊形式,又称为最优二叉树,其主要作用在于数据压缩和编码长度的优化。 2 重要概念 2.1 路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路...
  • 文章目录0. 从霍夫曼编码讲起1. 二叉树一些基本概念1.1. 路径1.2. 路径长度1.3. 节点的权1.4. 节点的带权路径长度1.5. 的带权路径长度2. Huffman的构建3. 代码实现(python)4. 应用 ...0. .
  • 霍夫曼树有两种实现方式:一种是基于链表的实现方式,另一种是基于动态数组的实现方式。 本文是基于动态数组的实现方式: 代码及结果展示: #include<stdio.h> #include<stdlib.h> #include<string...
  • matlab 霍夫曼树的生成与霍夫曼编码

    千次阅读 2019-05-11 01:36:05
    @matlab 霍夫曼树的生成与霍夫曼编码 %% --------------------------------------------- % code by WangYuan % date 2019/05/11 %---------------------------------------------------- %% function [ m3,e ...
  • 霍夫曼霍夫曼树的生成,编码,解码(C++) void init_link(Link *head);//初始化链表 void insert_link(Link head, HFMTree hfm);//向链表中插入一个元素,并按照权重排序 int delete_link(Link head,HFMTree *hfm);...
  • 数据结构--霍夫曼树与霍夫曼编码

    千次阅读 2019-07-08 20:44:37
    文章目录最优树的定义如何构造最优树(霍夫曼算法)霍夫曼编码前缀编码总结 最优树的定义 节点的路径长度定义为:从根节点到该节点的路径上分支的数目。 的路径长度定义为:中每个节点的路径长度之和。 的带权...
  • 数据结构之霍夫曼树

    2017-11-10 10:41:19
    首先就需要构建一个霍夫曼树,一般利用优先级队列来构建霍夫曼树 以上面的消息为例,我们先来分析一下构建霍夫曼树的过程,下图中,if代表换行符,sp代表空格 首先,将字符按照频率插入一个优先级队列,...
  • 针对内容寻址网络多区域失效导致的覆盖网结构破坏与子网割裂问题,提出了基于霍夫曼树的内容寻址网络失效恢复机制。采用霍夫曼树对覆盖网逻辑空间重新进行组织与优化,在失效结点检测机制的基础上,提出了单个区域与...

空空如也

空空如也

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

霍夫曼树