- 一、哈夫曼树
- 1.哈夫曼树：
- 2.哈夫曼树算法实现
- （1）存储结构：
- （2）算法实现：
- 建立哈夫曼树：
- select函数：
- 3.哈夫曼编译码
- （1）概念：
- （2）哈夫曼编码的算法实现：
树的带权路径的长度：
树中所有叶子结点的带权路径长度之和：
最优二叉树：在叶子结点个数n以及各个的权值以及各个叶子结点的权值W在确定的条件下，树的带权路径长度WPL值为最小的二叉树为最优二叉树。
1.哈夫曼树：（1）来源：由于哈夫曼最早给出建立最优二叉树的方法，因此最优二叉树又称为哈夫曼树。
（2）哈夫曼树的建立：
a. 初始化：根据给定的n个权值（W1，W2，… ，Wn）构造n棵二叉树的森林集合F={T1，T2，… ,Tn}其中每棵二叉树Ti,只有一个权值为Wi的根节点，左右子树皆为空。
b. 找到最小树并构造新树，在森林的集合F中选取两棵树的权值最小的树作为左右子树构造一棵新的二叉树，新二叉树的根节点为新增的结点，其权值为左右子树根的权值之和。
c.删除与插入。在森林集合F中删除已选取的两颗根的权值最小的树，同时将新构造的二叉树加入森林集合F，
重复步骤b和c，直至森林集合F中只含有一棵树为止，这棵树为哈夫曼树，即最优二叉树。将b和c步骤重复n-1次即可获得哈夫曼树。
a.哈夫曼树是二叉树可采用二叉树存储方法。
b.【静态的三叉链表】哈夫曼树中没有度为1的结点，这类二叉树又称正则二叉树。对于n个叶子打哈夫曼树，算法中构建了n-1个度为2的结点，所以哈夫曼树共有2n-1个结点，可以存储在2n-1的一维数组中。
c.三叉链表结点结构表示为：
| Weight | Parent | Lchild | Rchild |
|---|
d.其类型定义如下：
#define N30
#define M 2*N-1
typedef struct{
int Weight;
int Parent,Lchild,Rchild;
}HTNode,HuffmanTree[M+1];//0号元素不使用
（2）算法实现：
- 初始化所有结点，首先构造n个结点，即将数组前n个元素视为根节点，其权值为W，孩子和双亲指针全部置为0；其次置空后n-1个元素，初始时各域均置为0.
- 构造新的结点，构建哈夫曼树。在数组已有结点中选取双亲为0（即为树根）且权值最小的两个结点，构造其新结点，新结点下标为数组中已有结点的下一个位置，其权值为选取的两权值最小的结点的权值之和，其左右孩子分别为两权值最小的结点，并将两权值最小的结点的双亲改为指向新结点。此过程重复n-1次。
void CrtHuffmanTree(HuffmanTree ht,int w[],int n){
int m=2*n-1;
int i,s1,s2,m;
for( i=1;i<=n;i++){
ht[i].weight = w[i];
ht[i].parent = 0;
ht[i].Lchile = 0;
ht[i].Rchile = 0;
}
for(i=n+1;i<=m;i++){
ht[i].weight = 0;
ht[i].parent = 0;
ht[i].Lchild = 0;
ht[i].Rchild = 0;
}
for(i = n+1;i<=m;i++){
select(ht,i-1,&s1,&s2);
ht[i].weight = ht[s1].weight+ht[s2].weght;
ht[s1].parent = i;
ht[s2].parent = i;
ht[i].Lchile = s1;
ht[i].Rchild = s2;
}
}
select函数：
#define MASINT 32767
select(HuffmanTree ht,int pos,int *s1,int *s2){
int i,j,m1,m2;//m1存放最小权值，s1时m1在数组的下标
m1 = m2 = MAXINT;//m2存放次小权值，s2时m2在数组的下标
for(j=1;j*s2){
i = *s1;
*s1 = *s2;
*s2 = i;
}
}
3.哈夫曼编译码
（1）概念：
前缀编译码：同一字符集中任意一个字符的编码都不是另一个字符编码的前缀串（最左子串），这种编码称为前缀编码。
哈夫曼编码：时可以使信息压缩到最短的二进制前缀编码，即最优二进制前缀编码。
主要分为两大类：
- 构建哈夫曼树
- 在构建哈夫曼树上求各叶子结点的编码。
哈夫曼编码的长度不等，可以按编码的实际长度分配空间，但要使用一个指针数组存放每个编码的头指针，其定义如下：
typedef char * Huffmancode[n+1];
求哈夫曼树上的各叶子结点的编码：
- 从叶子结点开始，沿结点的双亲链追溯到根节点，追溯的过程中，每上升一层，则经过一条分支，便可以得到一位哈夫曼编码的值，左分支得到0，右分支得到1.
- 由于从叶子结点追溯到根的过程所得到的码串恰为哈夫曼编码的逆串，因此，在产生哈夫曼编码时，使用一个临时数组cd，每一位编码从后向前逐位放入cd中，由start 指针控制存放的次序。
- 达到根结点时，一个叶子的编码构造完成，此时将cd数组中以start 开始的串复制到动态申请的编码串空间即可。
代码实现：
void CrtHuffmanCode1(HuffmanTree ht,HuffmanCode hc,int n){//从叶子到根，逆向求各叶子结点的编码
char *cd;
int start;
cd = (char *)malloc(n*sizeof(char));//临时编码数组
cd[n-1] = ' ';
for(i=1;i
