带权路径长度最下的称为赫夫曼树(HuffmanTree)；
赫夫曼编码
在传送电文的时候希望，电文的总长度尽可能的短。可以做出这样的设计，对电文中的字符设计不同长度的编码，且让出现次数较多的字符采用尽可能短的编码。为了区分不同的编码，则必须任何一个字符的编码都不是另外一个编码的前缀。
赫夫曼树的构造方法
- 根据给定的n个权值{w1,w2,...,wn}构成n棵二叉树集合F={T1, T2, T3....}，其中每棵二叉树Ti中只有一个带权为wi的根节点。
- 在F中选取两颗根节点的权值最小的树作为左右孩子构建一颗新树，且新树的根节点的权值为其左右树上根节点的权值和
- 在F中删除这两棵树(即标记为已访问),并在F中添加新树
- 重复2，3直到F中只有一棵树，就得到了赫夫曼树
用w=[5,29,7,8,14,23,3,11]为例
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 5 | 29 | 7 | 8 | 14 | 23 | 3 | 11 |
1.找到权值最小的两个节点1，7，构成一颗新树，把新树添加到森林中，删除这两棵树
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 5 | 29 | 7 | 8 | 14 | 23 | 3 | 11 | 8 |
2.重复以上过程，红色背景表示已经访问过，再次找最小权值的时候，不再考虑这些节点
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 5 | 29 | 7 | 8 | 14 | 23 | 3 | 11 | 8 | 15 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 5 | 29 | 7 | 8 | 14 | 23 | 3 | 11 | 8 | 15 | 19 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 5 | 29 | 7 | 8 | 14 | 23 | 3 | 11 | 8 | 15 | 19 | 29 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 5 | 29 | 7 | 8 | 14 | 23 | 3 | 11 | 8 | 15 | 19 | 29 | 42 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 5 | 29 | 7 | 8 | 14 | 23 | 3 | 11 | 8 | 15 | 19 | 29 | 42 | 58 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 5 | 29 | 7 | 8 | 14 | 23 | 3 | 11 | 8 | 15 | 19 | 29 | 42 | 58 | 100 |
赫夫曼树中没有度为1的结点，则一棵有n个叶子结点的赫夫曼树一共有2*n-1个结点，可以用一个大小为2*n-1的数组来储存赫夫曼树。赫夫曼树构成后，为求编码需要从叶子结点出发找到一条从叶子结点到根的路径；为了译码则需要相反的路径；则对每个结点而言既要知道它双亲的信息，又要知道孩子结点的信息。
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 /* 5 author: Lai XingYu 6 date: 2018/5/17 7 describe: HuffmanCode 8 */ 9 typedef struct{ 10 unsigned int weight; 11 unsigned int parent, lchild, rchild; 12 bool vis; //标识该节点是否被访问过，方便找剩下树中权重最小的两棵树 13 }HTNode, *HuffmanTree; 14 15 typedef char** HuffmanCode; 16 17 void select(HuffmanTree HT, int pos, int& s1, int& s2){ 18 int j; 19 s1 = s2 = 0; 20 for(j=1; j<=pos; j++){//找到最小值 21 if(!HT[j].vis && (s1==0 || HT[s1].weight>HT[j].weight)) s1 = j; 22 } 23 for(j=1; j<=pos; j++){//找到次小值 24 if(j!=s1 && !HT[j].vis && (s2==0 || HT[s2].weight>HT[j].weight)) s2=j; 25 }//标识为已访问 26 HT[s1].vis=1; 27 HT[s2].vis=1; 28 } 29 30 /* 31 HC：用来保存生成的huffman code 32 n： 需要编码字符个数 33 HT：huffman 树 34 所有数组中的第一个空间都不使用 35 */ 36 void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int* w, int n){ 37 if(n<=1) return; //一位字符不需要进行编码 38 int m = 2*n-1, i; 39 HT = new HTNode[m+1]; 40 HTNode *p = HT+1; 41 for(i=1; i<=n; i++){//初始化 42 HTNode temp = {*w, 0, 0, 0, 0}; 43 *p = temp; 44 w++; 45 p++; 46 } 47 for(i=n+1; i<=m; i++){ 48 HTNode temp = {0, 0, 0, 0, 0}; 49 *p = temp; 50 p++; 51 } 52 int s1, s2; 53 for(i=n+1; i<=m; i++){//建立赫夫曼树 54 select(HT, i-1, s1, s2); //找未被访问过的权重最小的两个结点的位置 55 HT[i].lchild = s1; HT[i].rchild = s2; //把这两个结点作为当前结点的孩子 56 HT[s1].parent = i; HT[s2].parent = i; //自然这两个孩子的双亲是i 57 HT[i].weight = HT[s1].weight + HT[s2].weight; 58 } 59 60 HC = new char*[n+1]; 61 char *cd = new char[n]; 62 cd[n-1] = ' '; 63 for(i=1; i<=n; i++){//生成编码 64 int start = n-1, c=i, f=HT[i].parent; 65 for( ; f!=0; c=f, f=HT[f].parent){ //找到一条从叶子结点到根结点的路径就能求到该字符的编码 66 if(HT[f].lchild==c) cd[--start] = '0';//左结点表示0 67 else cd[--start] = '1';//右边节点表示1 68 } 69 HC[i] = new char[n-start]; 70 strcpy(HC[i], &cd[start]); 71 } 72 delete(cd); 73 } 74 75 int main(){ 76 HuffmanTree HT; 77 HuffmanCode HC; 78 int w[]={5,29,7,8,14,23,3,11}; 79 int n = 8; 80 HuffmanCoding(HT, HC, w, n); 81 for(int i=1; i<=n; i++) cout<<i<<" "<<HC[i]<<endl; 82 return 0;}