哈夫曼树构造方法，把一开始的各个点看作一颗颗树，取权值最小的两棵树组成一颗新二叉树，新树权值为两点之和，放入森林中取代原来的两个结点。一直重复直至只剩最后一颗树
哈夫曼编码方法，把各个字符作为结点，权值是字符出现的频率，构造出哈夫曼树，各个字符最终都出现在叶子节点上，然后从根节点到某字符的路径，向左为0，向右为1，得到哈夫曼编码



E为00

B为010

C++ 哈夫曼树和哈夫曼编码
哈夫曼树又称最优二叉树是树的结构应用之一。
哈夫曼树的构建：
从集合中选出最小的两个元素，相加和放入集合。再从集合中选出最小的两个元素，相加和放入集合…
不说了，直接上图


哈夫曼树的带权路径长度：
即叶结点权值 * 根结点到该叶结点的路径长度
路径长度：根结点到第L层结点的路径长度为L-1


哈夫曼编码
从结点开始，左分支路径记0，右分支路径记1，从根结点到目标叶结点路径上的编号序列就是哈夫曼编码

1、编程思想
哈夫曼树
哈夫曼树是最小的WPL值，也就是最小带权路径。编程就是将n个权值进行比较，用最小的两个组成一个新的节点。

用数组接收输入的n个节点的权值，将输入的编码进行整理，将最小的两个权值进行合并，多出n-1个新节点。用一个临时的数ct保存其左右子树以及父节点。通过临时的节点，将所有排序好的节点存放到tree[]数组中。
哈夫曼编码
对哈夫曼树中的前n个节点进行编码，从根节点开始，位于左子树的为0，右子树为1。编程就是通过符号找到其对应的是左子树还是有子树。

输入与权值对应的编码，找到code[]与tree[]之间的映射，从tree[]开始向上遍历。将编码整合到code[].bits[]中。并且输出编码表。
译码
译码就是通过输入的一串编码进行分割，在编码表中找到对应的匹配。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define n 5 
#define m 2*n-1
#define MIN 100 
typedef struct 
{
   float weight;
   int lchild,rchild,parent;
}hfmtree;
hfmtree tree[m];
typedef struct
{
   char bits[n];
   int start;
   char ch;
}codetype;
codetype code[n];

void hfm(void)
{
   //int n = 5; 
   int i,j,p1,p2;
   float s1,s2,f;
   //m个节点初始化
   for(i = 0;i<m;i++){
   	tree[i].parent = -1;
   	tree[i].lchild = -1;
   	tree[i].rchild = -1;
   	tree[i].weight = 0;
   }
   //输入n个节点的权值
   printf("请输入n个权值，空格隔开回车结束\n");
   for(i = 0;i<n;i++){
   	scanf("%f",&f);
   	getchar();
   	tree[i].weight = f;
   }
   //合并成m个节点
   for(i = n;i<m;i++){
   	p1 = -1;	//小的下标
   	p2 = -1;	//第二小的下标
   	s1 = MIN;	//小的权值
   	s2 = MIN+1;	//第二小的权值
   	//找出前面的最小权值和第二小权值
   	for(j =0;j<i;j++){
   		if(tree[j].parent == -1){
   			if(tree[j].weight<=s1){
   			s2 = s1;
   			s1 = tree[j].weight;
   			p2 = p1;
   			p1 = j;
   			}
   			else if(tree[j].weight<=s2){
   			s2 = tree[j].weight;
   			p2 = j;
   			}
   		}
   	}
   	tree[p1].parent = i;
   	tree[p2].parent = i;
   	tree[i].lchild = p1;
   	tree[i].rchild = p2;
   	tree[i].weight = tree[p1].weight+tree[p2].weight;
   	tree[i].parent = -1;
   }
   for(i=0;i<n;i++)
   	printf("第%d个的权值是%f\n",i,tree[i].weight);
}
void hfm_code(void)
{
   int i,j,p1,p2,k;
   char c;
   codetype ct;
   //输入对应的字符 
   printf("请输入对应的字符,空格隔开回车结束\n");
   for(i=0;i<n;i++){
   	scanf("%c",&c);
   	getchar();
   	code[i].ch = c;
   } 
   //编码0或者1 
   for(i=0;i<n;i++){
   	ct.start = n;
   	p1 = tree[i].parent;
   	p2 = i;
   	//从叶子开始编码
   	while(p1 != -1){
   		//n个节点最多有n-1个编码 
   		ct.start--;
   		if(tree[p1].lchild==p2)
   			ct.bits[ct.start] = '0';
   		else if(tree[p1].rchild==p2)
   			ct.bits[ct.start] = '1';
   		p2 = p1;
   		p1 = tree[p2].parent;	
   	}
   	//保存编码
   	k = 0;
   	for(j=ct.start;j<n;j++){
   		code[i].bits[k] = ct.bits[j];
   		k++;
   	}
   	code[i].start = ct.start;
   }
   //打印编码
   printf("编码表为\n");
   for (i=0; i<n; i++){
   	printf ("%c 's HFM code is: ", code[i].ch);
   	for (j=0;j<(n-code[i].start);j++){
   		printf ("%c", code[i].bits[j]);
   	}
   	printf ("\n");
   }
   
   
} 
//解码 
void hfm_decode(char arr[]) 
{
   int i,j,k;
   char temp[n];
   k = 0;
   i = 0;
   //遍历输入的编码，从编码表查找。 
   while(arr[i]!='\0'){
   	if(arr[i]=='\0')
   		break;
   	temp[k] = arr[i];
   	k++;
   	temp[k] = '\0';
   	//从编码表中找出相应的字符 
   	for(j=0;j<n;j++){
   		if(!(strcmp(temp,code[j].bits))){
   			k = 0;
   			printf("%c",code[j].ch);
   			break;
   		}
   	}
   	if(k>n)
   		printf("这串编码有问题，请重新检查！！\n"); 
   	i++;
   }
   printf("\n"); 
}

int main()
{
   int i = 0;
   char c,arr[1024];
   hfm();
   hfm_code();
   //输入需要解码的一串码 
   printf("请输入一段编码序列,Ctrl+Z结束\n");
   while(scanf("%c",&c)!=EOF){
   	arr[i] = c;
   	i++;
   }
   arr[i-1] = '\0';
   hfm_decode(arr);
   
   return 0;
}


运行结果

1 #include 
2 using namespacestd;3
4 const int max = 8;5
6 struct CodeNode {            //存储 编码的 0 1 字符串
7     charch;8     charbit[max];9     intlength;10 };11 struct HuffmanNode {        //HuffmanTree 的结点数据
12     chardata;13     intparent, lchild, rchild, weight;14 };15
16 classHuffmanTree {17 public:18 HuffmanTree();19     ~HuffmanTree();20     void _enCode(char *, int *, int);            //编码
21     void _deCode(char *);                        //译码
22     void _getMin(int, int &, int &);            //返回最小的两个 下标值: 索引长度 最小值 次小值
23     void _ShowdeCode();                            //将存储在数组中的元素输出 验证 是否成功编码
24     void _getIndex(int &, int &);25 private:26     HuffmanNode nodes[2 * max - 1];        //数组存储二叉树的所有结点数据
27     CodeNode charCode[max];                //数组存储二叉树结点编码的数据
28     char data_deColde[50];                //将翻译所得的字符放入其中
29     int nodeNumber;                        //有效结点的个数
30 };31
32 voidmain() {33
34     cout << "赫夫曼编码、译码：设置最大为 max = 8 个结点数据，最大存储译码字符为50个" <
39     char ch[100];40     int i = 0;41     cin >>ch[i];42     while (ch[i] != '#') {43         ++i;44         cin >>ch[i];45 }46
47 HT._deCode(ch);48 HT._ShowdeCode();49
50     system("pause");51 }52
53 HuffmanTree::HuffmanTree() {54     cout << "char 输入字符串结点：";55     chardata[max];56     cin >>data;57     cout << "int  输入各结点权值：";58     intwight[max];59     int i = 0;60     while (data[i] != '\0') {61         cin >> wight[i++];    //注意 i++ 表示先用再加, i 最后代表着这个数组的有效元素个数
62 }63     nodeNumber =i;64 _enCode(data, wight, i);65
66 }67 HuffmanTree::~HuffmanTree() {68     nodeNumber = 0;69 }70
71 void HuffmanTree::_deCode(char *ch) {72     int i = 0;73     int j = 1;74     int size = 0;75     bool flag = true;76     int index = 2 * nodeNumber - 2;        //下标，初始化是根所在下标 2 * nodeNumber - 2
77     while (ch[i] != '#') {                //对字符串一个个的匹配78         //只有当左右孩子下标为 -1 的时候表示已经到了叶子结点处，故对应了一个编码字符
79         while (nodes[index].lchild != -1 || nodes[index].rchild != -1) {80             if (ch[i] == '1') {            //字符 1 向右 否则为1 向左
81                 index =nodes[index].rchild;82 }83             else{84                 index =nodes[index].lchild;85 }86             if (ch[i] == '#') {                //为了：当用户未输入完代码时，将导致 下表 i 不能退出循环判断 ch[i]的值，故在此加上一个判断
87                 data_deColde[size++] = 22;    //由于是未输入完，加入其它字符(字符十进制为22的) 提示用户含有一个未解析的代码串
88                 flag = false;                //由于结束了，不再放入其它字符 flag置为 false， 而且 nodes[index].data也不是需要的字符
89                 break;90 }91             i++;92 }93         if (flag == true)94             data_deColde[size++] = nodes[index].data;    //将翻译获得的字符放入 data_deCode中
95         index = 2 * nodeNumber - 2;                        //再次返回到根下标去，即从根开始继续循环执行
96         if (nodeNumber == 1) ++i;                        //目的是为了： 当只编码一个 字符的时候，将不能执行 while循环而导致 i 永远为 初始值0，不能自加
97 }98     data_deColde[size] = '#';                            //作为输出结束符
99 }100
101 void HuffmanTree::_enCode(char * Data, int * Wight, intlen) {102     //初始化 nodes结点数组， 父、左、右全为 -1
103     int i = 0;104     while (Data[i] != '\0') {105         nodes[i].data =Data[i];106         nodes[i].weight =Wight[i];107         nodes[i].parent = nodes[i].lchild = nodes[i].rchild = -1;108         i++;109 }110     //创建 HuffmanTree
111     int m1, m2;    //m1 存储最小值 ， m2 其次
112     for (i = len; i < 2 * len - 1; ++i) {113 _getMin(i, m1, m2);114         nodes[i].lchild = m1;    //设置左、右 孩子 下标
115         nodes[i].rchild =m2;116
117         nodes[i].weight = nodes[m1].weight + nodes[m2].weight;    //设置 两结点之和后的父结点权值
118         nodes[i].parent = -1;    //暂无父结点 ，置为 -1
119         nodes[m1].parent = nodes[m2].parent = i;    //设置 左、右孩子的 父结点
120 }121
122     //对 HuffmanTree进行编码  左结点为1 右结点为0
123     for (i = 0; i < len; ++i) {124         int tem =nodes[i].parent;125         int m = i;    //m 作为孩子结点所在的下标,不能直接用 i，因为 i 表示的是叶子结点
126         charCode[i].ch =nodes[i].data;127         charCode[i].length =len;128         while (tem != -1) {    //parent == -1的只有根结点, i 到 len 的都是叶子结点
129             if (nodes[tem].lchild == m)        //当前结点 nodes[i]的是父结点的左孩子 为 1
130                 charCode[i].bit[--charCode[i].length] = '0';131             else                            //当前结点 nodes[i]的是父结点的右孩子 为 0
132                 charCode[i].bit[--charCode[i].length] = '1';133             m = tem;    //
134             tem =nodes[tem].parent;135 }136         //对编码以后的代码进行输出验证：
137         cout << charCode[i].ch << ":";138         for (int j = charCode[i].length; j < len; ++j) {139             cout <
145 void HuffmanTree::_getMin(int len, int& m1, int&m2) {146     bool flag = true;147     int min1 = INT_MAX, min2 =INT_MAX, tem;148     for (int i = 0; i < len; ++i) {149         if (nodes[i].parent == -1 && flag) {    //保留第一位未操作的元素
150             min1 =nodes[i].weight;151             m1 =i;152             flag = false;153 }154         else if (nodes[i].parent == -1) {155             if (nodes[i].weight 
169 }170 }171
172 voidHuffmanTree::_ShowdeCode() {173     int i = 0;174     cout << "译码：" <