哈夫曼树：给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。（来自百度百科）
用这样的二叉树表示最优前缀码，有两个重要的结论：
结论1：
n个叶子的二叉树一定对应一个前缀码。如果编码a为编码b的前缀，则a所对应的结点一定为b所对应结点的祖先。而两个叶子不会有祖先后代的关系。
结论2：
最优前缀码一定可以写成二叉树。逐个字符构造即可。每拿到一个编码，都可以构造出从根到叶子的一条路径，沿着已有结点走，创建不存在的结点。这样得到的二叉树不可能有单儿子结点，因为如果存在，只要用这个儿子代替父亲，，得到的仍然是前缀码，且总长度更短。
结论1称为贪心选择性质，结论2称为最优子结构性质。
Huffman算法：把每一个字符看作一个单节点子树放在一个树的集合中，每棵子树的权值等于相应字符的频率。每次取权值最小的两棵子树合并成一颗新树，并重新放到集合中，新树的权值等于两棵子树权值之和。
(以上参考算法经典入门1（刘汝佳）)
以下是代码：
# include <iostream># include <string>using namespace std;class Tree//构成树结点的类{public:char a;//节点的字符char t;//表示该位置为0或1的变量int flag;//标记该位置是否被取用过int height;//表示权值Tree *lchild, *rchild; //左右孩子的指针};Tree *p = new Tree[50]; //定义一个结构体数组，为子树集合int get_min()//从结构体中找出权值最低但不为0且没被取过的结点位置{int i = 0;while (p[i].height == 0 || p[i].flag == -1) //跳过前面无用的结点i++;int min = i;for ( ; i < 50; i++)//向后扫描筛选{if (p[i].height > 0){if (p[i].flag == 0 && p[i].height < p[min].height) //找权值最小但不为0的{min = i;}}}return min;}int is_empty1()//判断剩余的结点是否为1{int count = 0;for (int i = 0; i < 50; i++){if (p[i].flag == 0 && p[i].height > 0) //判断count++;}if (count > 1) //不为1return 1;else//为1return 0;}void mid_(Tree *root) //中序遍历Huffman树{Tree *p;p = root;if (p == NULL)return;if (p->lchild != NULL)mid_(p->lchild);cout << p->a << ' ';if (p->rchild != NULL)mid_(p->rchild);}class Huffman//Huffman类{public:Huffman(){}~Huffman(){}Tree *build_huffmanTree(); //构建Huffman树void Decoding(Tree *root); //解码void get_code();//获得需要编码的字符void get_decode();//获得需要解码的字符private:string code;//编码字符string decode;//解码字符};void Huffman::get_code(){cout << "输入大写字母进行编码 ： ";cin >> code;}void Huffman::get_decode(){cout << "输入需要解码的编码 : ";cin >> decode;}Tree *Huffman::build_huffmanTree(){int i, j, k = 26;//k位置为备用结点for (i = 0; i < 50; i++)//初始化结构体数组{p[i].height = p[i].flag = 0;p[i].lchild = p[i].rchild = NULL;if (i <= 25)//前面26个位置为各个大写字母p[i].a = 'A' + i;else//后面的为备用节点，字符为空格p[i].a = ' ';}int length = code.length();for (i = 0; i < length; i++)//统计各个字符出现的次数p[code[i] – 'A'].height++;while (is_empty1())//判断是否需要继续构建树{i = get_min();//获得一个最小权值的结点p[i].flag = -1;//标记为已经获得j = get_min();//再次获得一个权值最小的结点p[j].flag = -1;//标记p[k].lchild = (p + i);//备用结点左右孩子指向两个权值最小的p[k].lchild->t = '0';//左为0p[k].rchild = (p + j);p[k].rchild->t = '1';//右为1p[k++].height = p[i].height + p[j].height; //权值相加}p[k – 1].t = ' ';//根节点的t为空格return (p + k – 1);//返回根节点}char table[20];void gettable(int x, Tree *root)//递归获得编码表{Tree *p;p = root;table[x] = p->t;if (p->rchild == NULL && p->lchild == NULL) //为叶节点，输出编码{table[++x] = '\0';cout << p->a << ':' << table << endl;}if (p->lchild != NULL)//递归左右孩子gettable(x + 1, p->lchild);if (p->rchild != NULL)gettable(x + 1, p->rchild);}void Huffman::Decoding(Tree *root)//解码{Tree *p;char code[50];int flag = 0 , k = 0, i = 0;while (1){p = root;while (p->lchild != NULL || p->rchild != NULL) //不是叶子节点{if (decode[i] == '0')//0进去左孩子{p = p->lchild;if (p == NULL)//进去为空指针，表示出错了，标记flag = 1flag = 1;}if (decode[i] == '1')//1进去右孩子{p = p->rchild;if (p == NULL)//同上flag = 1;}i++;if ((p->lchild != NULL || p->rchild != NULL) && i >= decode.length()) //解码字符串到尾了，指针没到叶子节点flag = 1;//flag = 1if (flag)//标记flag = 1，终止break;}if (flag)//flag = 1，终止break;code[k++] = p->a;//将翻译得到的叶子结点的a复制过去。if (decode[i] == '\0')//解码字符串到了最后一个位置{code[k] = '\0';//加上字符串结束标志break;}}if (flag)//没有出错，输出解码的字符串，否则，输出出错信息cout << "Input Error!" << endl;elsecout << "The result of the decode : " << code << endl;}int main(){Huffman A;Tree *root;A.get_code(); root = A.build_huffmanTree();//构建Huffman树mid_(root);//中序遍历cout << endl;gettable(0, root);//获得编码表while (1){A.get_decode();A.Decoding(root);//解码操作}return 0;}我写的这个，是只能输入大写字母的，输入其他字符会出错的，加上其他的字符也是同样的，只是增大数组和一些地方需要改动而已。代码中清楚的讲解了如何实现和个别代码的讲解和解释。如果有什么错误，欢迎指正。~
下面的是运行结果的图：
生活中若没有朋友，就像生活中没有阳光一样
