实验题：构造哈夫曼树生成哈夫曼编码
 编写一个程序，构造一棵哈夫曼树，输出对应的哈夫曼编码和平均查找长度，并对下表（所示的数据进行验证。
 
单词及出现的频度
 单词： 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;
}
 
运行结果：
 
 如果本文对你有帮助的话，请👍哦(●ˇ∀ˇ●)

哈夫曼树的构建
 
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();
    }
}

哈夫曼树（最优二叉树）
 
百度百科：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
 
第一步：找出字符中最小的两个，小的在左边，大的在右边，组成二叉树。在频率表中删除此次找到的两个数，并加入此次最小两个数的频率和。
 
F和G最小，因此如图，从字符串频率计数中删除F与G，并返回G与F的和 8给频率表
 
 
 重复第一步：
 
-------------------------------------------------------------------------------------------------
 
频率表 A：60,    B:45,   C:13   D:69   E:14   FG:8
 
最小的是 FG：8与C：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
 
每个 字符 的 二进制编码 为（从根节点 数到对应的叶子节点，路径上的值拼接起来就是叶子节点字母的应该的编码）
 
字符
编码
A
10
B
01
C
0011
D
11
E
000
F
00101
G
00100
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
那么当我想传送 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就好了～ 提出，在这里对他表示感谢。
 
 
 
 
 
 
 
看懂的朋友留个赞，没看懂的留言我给你单独讲 _(:з」∠)_

哈夫曼树是构建哈夫曼编码的一种方法，构造方式如下：
 
如有队列 {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)