结果展示：
哈夫曼树编码
1：编码方式
定长编码方案：每个字符的编码长度一样，如ASCII码，128个字符，都是用8位二进制码表示的，最高位为0，每个字符的编码与频率无关；这种使用方法可以很明显的明白并没有空间与时间概念而言，每一个数据定长，那么就会导致发送效率降低以及需要更长的缓冲区来存储这个数据。
例如定长发送数据AABC，那么其二进制编码为1000001100000110000101000011，也就是发送的数据长度为n*8bit。
变长编码方案：每个字符的编码长度与其出现的频率有关，出现的频率越高，其二进制编码的长度越越短；频率越低，则二进制编码长度越长；最后总数据的编码长度最短，实现压缩数据。
同样是发送AABC，使用变长发送数据其可能的编码是001011，对比上面的可以发现效率不止高了一点。
当然，看完上面你可能很疑惑为什么是001011，那么就需要来讲解一下哈夫曼树是如何生成的了。
2：带权二叉树
哈夫曼树是一种带权的二叉树，也就是每一个路径上都有其对应的权值
如节点N1到节点A与节点E，其中权值就是该条路径上的对应的数值5与10.。
也正是由于哈夫曼树的生成是通过带权路径长度最小的二叉树而得到的，因此其最高出现频率的数据将会在数的最上方，最低的则在树的下方，因此高频率数据将得到较短的编码，反之1低频率数据的编码较长。
3：哈夫曼树的创建过程
至此二叉树的创建就已经完成了，那么如何通过这个二叉树得到编码呢？
我们可以将图中的权值左分支改为0，右分支改为1后的哈夫曼树。如下：
之后我们就可以用六个字母用其从树根到叶子所经过的路径的0或1编码，可以得到如下的一张字母定义表：
可以发现对比使用定长编码的方法，新的二进制串节约了一定的存储或传输成本。并且随着数据的增加这种优势会更加明显。
但是，发送过来的数据是这样的，那么我如何解码呢？
很明显我们需要在编码和解码时使用同一种的编码协议。
因为哈夫曼树虽然是WPL最小的树，但是最小的情况不唯一，情况如下
可以发现虽然他们的WPL一样，但是字母对应的编码却不同，因此WPL一样的二叉树能生成的编码不唯一，因此我们需要规定解码和编码的协议，例如解码和编码都以左边的哈夫曼树为基准。
如何实现哈夫曼以及解码
思路：
上面已经大致介绍了哈夫曼树的概念，下面就来用方法来实现它。
首先我们需要思考如何存储每一个节点，因为我们不仅仅需要的是哈夫曼树，而是哈夫曼树形成后其每个数据对应的哈夫曼编码。编码的得到就需要判断是左孩子还是右孩子才能知道是1还是0，因此我们需要一个存放节点数据的结构体，其中需要包括左孩子，右孩子，双亲(便于从底层往高层得到编码值)，权值。
我们可以使用数组或链表存储，当然，明显这种判断结构使用数组会更方便实现一点。
数组中每一个元素用来存放该节点的信息以及自己的双亲和孩子节点，由于是int类型，直接去数组下标对应的位置取出数据即可。假设我们有n个数据要插入二叉树，那么我们的数组大小就应该是2n-1，因为每个数据会生成一个小二叉树，也就是2n，但是头节点只有一个，所以他不是2，而是1，因此需要-1.
以如下的数据插入二叉树，将形成如下数组。
我们定义如下的结构体数组来实现上图对应的二叉树。
typedef struct HuffManTree { int weigth; //权值 int parent, lchild, rchild;//双亲以及左右孩子 }HuffManTree,*p_HuffManTree;
之后就是如何往数组里填数据了。
根据哈夫曼树的构造方法，先抽出数组中最小的两个权值对应的下标，然后合成一个新的节点，新的节点占据数组的一个位置，并且将自己个数据导入数组，同时也可以发现左右子树为0的都是我们叶子节点，也就是我们最初的八个数据。
取两最小：
按照上面我们的思路，我们需要将从n+1开始的剩下的n-1个数组空位赋值，赋值方法按照上面的方法。
即取两最小合成新节点，循环往复n-1次即可，因此我们需要先写一个得到最小两个数据的函数
//用于找到两个最小的权值 m1和m2指针传递回最小两个值 void FindTwoMin(p_HuffManTree T, int n, int* m1, int* m2) { int min1, min2; //定义两个存放最小数据的整型 min1 = min2 = T[0].weight; //最小值初始化 for (int i = 1; i < n; i++)//第一个for循环遍历一次 得到最小min1 { if (T[i].weight < min1) { min1 = T[i].weight; *m1 = i; //将最小的数据的下标赋值给指针 } } for (int i = 1; i < n; i++)//第二个for循环遍历一次，得到最小min2 { if (T[i].weight < min2 && T[i].weight != min1)//判断条件 不能等于最小且不能是初始化值 { min2 = T[i].weight; *m2 = i; //将最小的数据的下标赋值给指针 } } //cout << *m1 << *m2 ; }
数组初始化：
通过调用找最小的两个数据的下标，我们可以吧数组完全初始化为上面的图片那样，到此为止数组初始化就完毕了，这是最后填充好数据的数组
void InitHuffManTree(p_HuffManTree T, int n) { int i; int* m1, * m2; m1 = (int*)malloc(sizeof(int)); //开辟两个存放最小数据下标的指针 m2 = (int*)malloc(sizeof(int)); if (n < 1) { cout << "初始化错误" << endl; exit(-1); } for (i = 0; i < 2 * n - 1; i++)//初始化为全0 { T[i].lchild = 0; T[i].parent = 0; T[i].rchild = 0; } cout << "输入权值" << endl; for (i = 0; i < n; i++)//初始化节点权值 { cin >> T[i].weight; } for (i = n + 1; i < 2 * n - 1; i++)//这段代码用于将两个最小合并成一个新结点，补充数组 { FindTwoMin(T, i-1 , m1, m2); //找到最小两个数据的下标此时以及初始化的数据有n个也就是i-1个 T[*m1].parent = i; T[*m2].parent = i; //让最小两个节点的双亲指向这个新数组下标 T[i].weight = T[*m1].weight + T[*m2].weight; //让两个数据的权值相加变为新结点权值 T[i].lchild = *m1; T[i].rchild = *m2; //左孩子指向最小数据的下标，右孩子指向第二小的 } }
编码实现：
实现完成数组之后我们就要想方设法的实现如何生成编码了，设置左孩子为0，右孩子为1
那么上图可得到对应数据的编码如下：
A:00 B:01 C:11 D:1001
E:1010 F:1011 G:10000 H:10001
之后就是我们应该是从对应的字符往上遍历直到根节点，这是因为如果你要找字符G，但是路径上有很多的左右结点，你并不知道G是在那一条路径上，因此先找到字符，然后往上找更简单，效率更高。
那么如果我们从下往上找，可以得到G的编码为01011，但是这个是与正常的相反的，因此我们倒序插入，正序输出。
那么接下来就是重头戏编码的创建了
编码创建：
//这段代码用来实现哈夫曼编码 编码个数为初始节点个数num(main中定义) //同时我们需要做到从下向上遍历，左孩子为0右孩子为1这标志放入一个数组(大小为n) void CreateHuffmanCode(p_HuffmanTree T,char** codearr ,int num) { int p; //用于指向当前节点的双亲结点在数组的下标位置 int j; //j用来表示当前结点所在数组的位置 int start; //编码数组的下标，每存放一个数据向前移动一位 char* code = new char[num]; //生成一个存放编码的数组(倒序编码，从下往上的) code[num - 1] = '\0'; for (int i = 0; i < num; i++) { j = i; //赋值当前结点位置 start = num - 1;//初始位置应该是n-1 p = T[i].parent;//当前节点的双亲节点，循环向上得到各双亲结点 while (p != 0) //我们直到最后一个结点它的parent是0，因此如果遇到了0说明到了根节点 { --start; if(T[p].lchild==j) //判断是否是左孩子 { code[start] = '0'; //左孩子为0 } else { code[start] = '1'; //右孩子为1 } j = p; //当前结点变为双亲结点位置 p = T[p].parent; //结点变为双亲节点 回溯 } codearr[i] = new char [num-start]; //开辟一个刚刚好能存放编码的数组 strcpy(codearr[i], &code[start]); //把编码数组的其实地址放入到二维数组中去 } delete code;//释放空间 }
代码中的解释比较全面了， 不多加解释了哈。
最后就是显示出数据的代码。
数据显示：
//这段代码用来输出哈夫曼树各节点信息 void ShowHuffmanTree(const p_HuffmanTree T,int n,char**codearr) { cout << "weight parent lchild rchild" << endl; for (int i = 0; i < 2 * n - 1; i++)//输出各种属性 { cout << T[i].weight << setw(10)<< T[i].parent << setw(10) << T[i].lchild << setw(10) << T[i].rchild << endl; } for (int i = 0; i < n; i++) //下面就是二维数组的输出数据的方法 { for (int j = 0; codearr[i][j] != '\0'; j++) { cout << codearr[i][j]; } cout << endl; } }
源代码：
algo.h文件的内容：
#pragma once #include<iostream> #include <cstdio> #include<cstdlib> typedef int Status; typedef int ElemType; typedef char cElemType; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXSIZE 20 #define make (struct student*)malloc(sizeof(struct student)); using namespace std;
代码部分：
#include <algo.h> #include<iomanip> typedef struct HuffmanTree { int weight; //权值 int parent, lchild, rchild;//双亲以及左右孩子 }HuffmanTree,*p_HuffmanTree; //用于找到两个最小的权值 m1和m2指针传递回最小两个值 void FindTwoMin(p_HuffmanTree T, int n, int* m1, int* m2) { int min1, min2; //定义两个存放最小数据的整型 min1 = min2 = 300; //最小值初始化 for (int i = 0; i < n; i++)//第一个for循环遍历一次 得到最小min1 { if (T[i].weight < min1 && T[i].parent == 0) { min1 = T[i].weight; *m1 = i; //将最小的数据的下标赋值给指针 } } for (int i = 0; i < n; i++)//第二个for循环遍历一次，得到最小min2 { //这个if这样写的原因是由于如果我输入4 3 2 1 由于1+2=3 那么就会有两个3 //如果单纯只有一个T[i].weight != min1 //那么由于新生成的3不能等于输入的3，那么这个3就会被忽略，而导致3+4=7 //而本来应该是3+3=6的 if (T[i].weight < min2 && (T[i].weight != min1 || (i>*m1 && T[i].weight==min1)) && T[i].parent == 0)//判断条件 不能等于最小且不能是初始化值 { min2 = T[i].weight; *m2 = i; //将最小的数据的下标赋值给指针 } } } void InitHuffmanTree(p_HuffmanTree T, int n) { int i; int* m1, * m2; m1 = (int*)malloc(sizeof(int)); //开辟两个存放最小数据下标的指针 m2 = (int*)malloc(sizeof(int)); if (n < 1) { cout << "初始化错误" << endl; exit(-1); } for (i = 0; i < 2 * n - 1; i++)//初始化为全0 { T[i].lchild = 0; T[i].parent = 0; T[i].rchild = 0; } cout << "输入权值" << endl; for (i = 0; i < n; i++)//初始化节点权值 { cin >> T[i].weight; } for (i = n ; i < 2 * n - 1; i++)//这段代码用于将两个最小合并成一个新结点，补充数组 { FindTwoMin(T, i , m1, m2); //找到最小两个数据的下标此时以及初始化的数据有n个也就是i-1个 T[*m1].parent = i; T[*m2].parent = i; //让最小两个节点的双亲指向这个新数组下标 T[i].lchild = *m1; T[i].rchild = *m2; //左孩子指向最小数据的下标，右孩子指向第二小的 T[i].weight = T[*m1].weight + T[*m2].weight; //让两个数据的权值相加变为新结点权值 } } //这段代码用来输出哈夫曼树各节点信息 void ShowHuffmanTree(const p_HuffmanTree T,int n,char**codearr) { cout << "weight parent lchild rchild" << endl; for (int i = 0; i < 2 * n - 1; i++)//输出各种属性 { cout << T[i].weight << setw(10)<< T[i].parent << setw(10) << T[i].lchild << setw(10) << T[i].rchild << endl; } for (int i = 0; i < n; i++) //下面就是二维数组的输出数据的方法 { for (int j = 0; codearr[i][j] != '\0'; j++) { cout << codearr[i][j]; } cout << endl; } } //这段代码用来实现哈夫曼编码 编码个数为初始节点个数num(main中定义) //同时我们需要做到从下向上遍历，左孩子为0右孩子为1这标志放入一个数组(大小为n) void CreateHuffmanCode(p_HuffmanTree T,char** codearr ,int num) { int p; //用于指向当前节点的双亲结点在数组的下标位置 int j; //j用来表示当前结点所在数组的位置 int start; //编码数组的下标，每存放一个数据向前移动一位 char* code = new char[num]; //生成一个存放编码的数组(倒序编码，从下往上的) code[num - 1] = '\0'; for (int i = 0; i < num; i++) { j = i; //赋值当前结点位置 start = num - 1;//初始位置应该是n-1 p = T[i].parent;//当前节点的双亲节点，循环向上得到各双亲结点 while (p != 0) //我们直到最后一个结点它的parent是0，因此如果遇到了0说明到了根节点 { --start; if(T[p].lchild==j) //判断是否是左孩子 { code[start] = '0'; //左孩子为0 } else { code[start] = '1'; //右孩子为1 } j = p; //当前结点变为双亲结点位置 p = T[p].parent; //结点变为双亲节点 回溯 } codearr[i] = new char [num-start]; //开辟一个刚刚好能存放编码的数组 strcpy(codearr[i], &code[start]); //把编码数组的其实地址放入到二维数组中去 } delete code;//释放空间 } int main() { int num; cout << "输入节点个数" << endl; cin >> num; char** codearr = new char*[num]; //二维数组 用来存放所有的编码 以便之后输出 p_HuffmanTree T = new HuffmanTree[2 * num - 1]; //创建二叉树节点数组 InitHuffmanTree(T, num); //初始化二叉树 CreateHuffmanCode(T, codearr, num); //创建二叉树编码 ShowHuffmanTree(T, num,codearr); //显示编码 }
