一．背景介绍：
　　给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到小，称这样的二叉树为优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度短的树，权值较大的结点离根较近。
　　二．实现步骤：
　　1.构造一棵哈夫曼树
　　2.根据创建好的哈夫曼树创建一张哈夫曼编码表
　　3.输入一串哈夫曼序列，输出原始字符
　　三．设计思想：
　　1.首先要构造一棵哈夫曼树，哈夫曼树的结点结构包括权值，双亲，左右孩子；假如由n个字符来构造一棵哈夫曼树，则共有结点2n-1个；在构造前，先初始化，初始化操作是把双亲，左右孩子的下标值都赋为0；然后依次输入每个结点的权值
　　2.第二步是通过n-1次循环，每次先找输入的权值中小的两个结点，把这两个结点的权值相加赋给一个新结点，，并且这个新结点的左孩子是权值小的结点，右孩子是权值第二小的结点；鉴于上述找到的结点都是双亲为0的结点，为了下次能正确寻找到剩下结点中权值小的两个结点，每次循环要把找的权值小的两个结点的双亲赋值不为0（i）.这样通过n-1循环下、操作，创建了一棵哈夫曼树，其中，前n个结点是叶子（输入的字符结点）后n-1个是度为2的结点
　　3.编码的思想是逆序编码，从叶子结点出发，向上回溯，如果该结点是回溯到上一个结点的左孩子，则在记录编码的数组里存“0”，否则存“1”，注意是倒着存；直到遇到根结点（结点双亲为0），每一次循环编码到根结点，把编码存在编码表中，然后开始编码下一个字符（叶子）
　　4．译码的思想是循环读入一串哈夫曼序列，读到“0”从根结点的左孩子继续读，读到“1”从右孩子继续，如果读到一个结点的左孩子和右孩子是否都为0，如果是说明已经读到了一个叶子（字符），翻译一个字符成功，把该叶子结点代表的字符存在一个存储翻译字符的数组中，然后继续从根结点开始读，直到读完这串哈夫曼序列，遇到结束符便退出翻译循环
　　四．源代码：
1 /***************************************
2 目的：1.根据输入的字符代码集及其权值集，
3 构造赫夫曼树，输出各字符的赫夫曼编码
4 2.输入赫夫曼码序列，输出原始字符代码
6 ****************************************/
7 #include<iostream>
8 #define MAX_MA 1000
9 #define MAX_ZF 100
10 using namespace std;
11
12 //哈夫曼树的储存表示
13 typedef struct
14 {
15     int weight;  //结点的权值
16     int parent， lchild， rchild;//双亲，左孩子，右孩子的下标
17 }HTNode，*HuffmanTree;  //动态分配数组来储存哈夫曼树的结点
18
19 //哈夫曼编码表的储存表示
20 typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码
21
22 //返回两个双亲域为0且权值小的点的下标
23 void Select(HuffmanTree HT， int n， int &s1， int &s2)
24 {
25     /*n代表HT数组的长度
26     */
27
28    //前两个for循环找所有结点中权值小的点（字符）
29     for (int i = 1; i <= n; i++)
30     {//利用for循环找出一个双亲为0的结点
31         if (HT[i].parent == 0)
32         {
33             s1 = i;//s1初始化为i
34             break;//找到一个后立即退出循环
35         }
36     }
37     for (int i = 1; i <= n; i++)
38     {/*利用for循环找到所有结点（字符）权值小的一个
39      并且保证该结点的双亲为0*/
40         if (HT[i].weight < HT[s1].weight && HT[i].parent == 0)
41             s1 = i;
42     }
43     //后两个for循环所有结点中权值第二小的点（字符）
44     for (int i = 1; i <= n; i++)
45     {//利用for循环找出一个双亲为0的结点，并且不能是s1
46         if (HT[i].parent == 0 && i != s1)
47         {
48             s2 = i;//s2初始化为i
49             break;//找到一个后立即退出循环
50         }
51     }
52
53     for (int i = 1; i <= n; i++)
54     {/*利用for循环找到所有结点（字符）权值第二小的一个，
55      该结点满足不能是s1且双亲是0*/
56         if (HT[i].weight < HT[s2].weight && HT[i].parent == 0 && i!= s1)
57             s2 = i;
58     }
59
60 }
61
62 //构造哈夫曼树
63 void CreateHuffmanTree(HuffmanTree &HT， int n)
64 {
65 /*-----------初始化工作-------------------------*/
66     if (n <= 1)
67         return;
68     int m = 2 * n - 1;
69     HT = new HTNode[m + 1];
70     for (int i = 1; i <= m; ++i)
71     {//将1~m号单元中的双亲，左孩子，右孩子的下标都初始化为0
72         HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0;
73     }
74     for (int i = 1; i <= n; ++i)
75     {
76         cin >> HT[i].weight;//输入前n个单元中叶子结点的权值
77     }