引子
当操作的数目很大的时候，有时候只需要改变一下判断的顺序，可以减少执行时间，两种判别树的效率是不一样的。
哈夫曼树就是一种效率最高的判别树，也称之为最优二叉树。
一、哈夫曼树的基本概念
- 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。
- 结点的路径长度：两个结点路径上的分支数。
- 数的路径长度：从树根到每一个节点的路径长度之和。记作：TL
- 结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树。
- 权：将树中结点赋给一个存有某种含义的数值，则这个数值称为该结点的权。
- 结点的带权路径长度：从根节点到该结点之间的路径长度与该结点的权的乘积。
- 树的带权路径长度：树中所有的叶子结点的带权路径长度之和。
例子：
哈夫曼树就是带权路径长度最短的树。
如何构造哈夫曼树？
构造方法如下：
具有相同带权结点的哈夫曼树不唯一。
例子一：
包含n棵树的森林要经过n-1次结合才能形成哈夫曼树，共产生n-1个新节点。所以包含n个叶子节点的哈夫曼树中共有2n-1个及结点。且哈夫曼树的节点的度数只有0或2，没有1.
例子二：
二、哈夫曼树的存储结构
- 采用顺序存储结构----一维结构数组
- 结点类型定义
存储结构如下所示：
typedef struct{ int weight; //权值 int parent,lch,rch; //双亲结点，左孩子结点，右孩子结点 }HTNode,*HuffmanTree;
构建哈夫曼树思路
例子：
哈夫曼树初始化与实现
伪代码如下,比较容易理解：
void CreateHuffmanTree(HuffmanTree HT,int n){ if(n <= 1) return; m = 2*n-1; //数组共2n-1个元素 HT = new HTNode[m+1]; //HT[m]表示根节点 for(i = 1; i < m; i++){ //将2n-1个元素的lch，rch，parent置0 HT[i].lch = 0; HT[i].rch = 0; HT[i].parent = 0; } for(i = 1; i < m; i++){ //输入前n个元素的weight值 cin >> HT[i].weight; } for(i = n+1; i < m; i++){ //合并产生n-1个结点 Select(HT, i-1, s1,s2); //选择两个双亲为0且权值为最小的结点，返回在HT中的s1,s2序号 HT[s1].parent = i;HT[s2].parent = i; //从表中删除s1,s2 HT[i].lch = s1;HT[i]rlch = s2; //s1,s2分别作为i的左右孩子 HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权值为左右孩子权值之和 } }
三、哈夫曼编码
如何编码使得电文总长最短？ -----哈夫曼编码
例子：如上编码就不会有歧义
特点：
- 哈夫曼编码能够保证是前缀编码，因为每一个结点路径都是不一样的；
- 哈夫曼树能保证字符编码总长度最短，因为本来哈夫曼树的带权路径长度最短。
四、哈夫曼编码算法实现
从底层反推到跟结点，判断是是左孩子还有孩子，然后标志01.
cd[start]：用来不断的存储标志01
HC[i]：用来存储结果
HT[i]：哈夫曼树结构
代码实现：
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n){ //从叶子到跟逆向求每个字符的哈夫曼编码，存储到编码表中 HC = new char* [n+1]; //分配n个字符编码的头指针矢量 cd = new char[n]; //分配临时存放编码的动态数组空间 cd[n-1] = '\0'; //编码结束符 for(i = 1; i <= n; i++) { start = n-1; c = i; f = HT[i].parent; while( f != 0) //当还不是根节点时一直回溯 { start--； if(HT[f].lchild == c) //结点c是f的左孩子，则生成代码0 cd[start] = '0'; else //结点c是f的右孩子，则生成代码1 cd[start] = '1'; c = f; //以下两步是回溯的作用 f = HT[f].parent; //自己成为双亲再查找 } HC[i] = new char[n - start];//为第i个字符串编码分配空间 strcpy(HC[i],&cd[start]); //将求得的编码从临时空间cd复制到HC的当前行中 } delete cd; //释放临时空间 }
五、哈夫曼编码-文件的编码和解码
- 编码实现过程
- 解码实现过程
- 例子
