【数据结构】哈夫曼树

哈夫曼树

路径长度：从树中一个结点到另一个结点之间的分支构成这两个节点之间的路径，路径上的分支数目称为路径长度

树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记为WPL=${\sum }_{k=1}^n{w}_k{l}_k$

带权路径长度最小的二叉树称为最优二叉树或哈夫曼树

注意：

哈夫曼树不一定是完全二叉树

书中一定没有度为1的结点

树中权值最小的两个结点一定是兄弟

包含n个叶子节点的哈夫曼树共有2n-1个结点

包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共形成n-1个新结点，且度为2

树中任意非叶子节点的权值一定不小于下一层任意结点的权值

哈夫曼树的构造

哈夫曼算法：

1. 根据给定的权值构成n棵二叉树的森林，每棵树只有一个带权为wi的根节点
2. 在森林中选取两棵根节点权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根节点的权值为其左右子树的权值和
3. 在森林中删除这两棵树，同时将新得到的二叉树加入森林中
4. 重复（2）（3），直到森林中只有一棵树为止，这棵树即为哈夫曼树（重复第二步时不一定选用新树）

哈夫曼树的实现

采用顺序存储结构

typedef struct{int weight;int parent,lch,rch;
}HTNode,*HTree;

void CreateHuffmanTree(HuffmanTree HT,int n){if(n<=1)return;m=2*n-1;//数组共2n-1个元素HT=new HTNode[m+1];//0号单元未用，HT[m]表示根节点for(i=1;i<=m;i++){	//将2n-1个元素的lch、rch、parent置为0HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;}for(i=1;i<=n;++i)cin>>HT[i].weight;//输入前n个元素的weight值//初始化结束，下面开始建立哈夫曼树for(i=n+1;i<=m;i++){	//合并产生n-1个结点——构造Huffman树Select(HT,i-1,s1,s2);//在HT[k]中选择两个双亲域为0，且权值最小的结点，并返回它们在HT中的序号s1和s2HT[s1].parent=i;HT[s2].parent=i;	//表示从F中删除s1、s2HT[i].lch=s1;	HT[i].rch=s2;	//s1,s2分别作为i的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight;//i的权值为左右孩子权值之和}
}

哈夫曼编码

将编码设计为不等长的二进制编码，让代传字符中出现次数较多的字符采用较短的编码

前缀编码：任一个字符的编码都不是另一个字符的字符的编码的前缀

构造哈夫曼编码：

1. 将字符出现的频率作为权值，构建哈夫曼树
2. 从根节点出发，左分支标记0，右分支标记1
3. 从根节点出发，到叶子节点，路过的所有分支的编码组合起来，就是哈夫曼编码