哈夫曼树（最优⼆叉树）、哈夫曼编码在此祝⼤家新年快乐，新的⼀年守住头发，不断进步！
哈夫曼树
⼀、哈夫曼树基本概念
（1）路径：从树中的⼀个结点到另⼀个结点之间的分⽀构成这两个结点之间的路径 （3）树的路径长度：从树根到每⼀结点的路径长度之和。
（4）权：将树中结点赋给⼀个有着某种含义的数值，则这个数值称为该结点的权。
（5）结点的带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积
超固态（6）树的带权路径长度：树中所有叶⼦结点的带权路径长度之和。
看以下⼏个例⼦：
我们可以总结出：
哈夫曼树：最优⼆叉树（带权路径长度（WPL）最短的⼆叉树） ，带权路径长度最短是在“度相同”的树中⽐较⽽得的结果，因此有最优⼆叉树、最优三叉树之称。
满⼆叉树不⼀定是哈夫曼树
哈夫曼树中权越⼤的叶⼦离根越近
具有相同带权结点的哈夫曼树不唯⼀
根据权值越⼤的结点离根结点越近这个特点，哈夫曼最早给出了⼀个构造哈夫曼树的⽅法，称为哈夫曼算法音乐什么时候传入中国
⼆、哈夫曼树的构造算法
典型的贪⼼算法：构造哈夫曼树时⾸先选择权值⼩的叶⼦结点。
哈夫曼算法（构造哈夫曼树的⽅法）
（1）根据n个给定的权值{w1,w2,w3…，wn}构成n棵⼆叉树的森林F={T1,T2,…,Tn}，其中，Ti只有⼀个带权为wi的根结点。
构造森林全是根
（2）在F中选取两棵根结点的权值最⼩的数作为左右⼦树，构造⼀棵新的⼆叉树，且设置新的⼆叉树的根结点的权值为其左右⼦树上根结点的权值之和
选⽤两⼩造新树
（3）在F中删除这两棵树，同时将新得到的⼆叉树加⼊森林中。
删除两⼩添新⼈
（4）重复（2）和（3），直到森林中只有⼀棵树为⽌，这棵树即为哈夫曼树。
重复2、3剩单根
例如：
（1）4个结点
（2）5个结点
新添加的结点都是度为2的结点。
总结：
（1）哈夫曼树的结点的度数为0或2，没有度为1的结点
（2）包含n个叶⼦结点的哈夫曼树中共有2n - 1个结点（每两个合并成为⼀个新结点，共合并n-1次）（3）新⽣成的结点有两个孩⼦（度为2）
三、哈夫曼树构造算法的实现
采⽤顺序存储结构——⼀维结构数组
结构类型定义
typedef struct{
int weight;//结点的权值
int parent,lch,rch;//结点的双亲、左孩⼦、右孩⼦的下标
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
HuffmanTree H;//定义⼀个指针变量
例如，第⼀个节点权值为5，表⽰为H[i].weight=5
哈夫曼树中共有2n-1个结点，不使⽤0下标，数组⼤⼩为2n.
三、哈夫曼构造算法的实现
【算法步骤】
1. 初始化HT[1,2…2n-1]:lch=rch=parent=0;
2. 输⼈初始n个叶⼦结点：置HT[1,2…n]的weight值；
3. ==进⾏以下n-1次合并，⼀次产⽣n-1个结点HT[i],i=n+1…2n-1;
a)在HT[1…i-1]中选两个未被选过的weight最⼩的两个结点HT[s1]和HT[s2]，s1,s2为两个最⼩结点下标；
期刊刊次
b)修改 HT[s1]和HT[s2]的parent值：HT[s1].parent=i;HT[s2].parent=i;
c)修改新产⽣的HT[i]:
HT[i].lch=s1;
HT[i].rch=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
【算法实现】
#include<iostream>
using namespace std;
typedef struct{
int weight;//结点的权值
int parent,lch,rch;//结点的双亲、左孩⼦、右孩⼦的下标
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
void CreatHuffmanTree(HuffmanTree &HT,int n)
忏悔录奥古斯丁{//构造哈夫曼树HT
if(n<=1)
return;
m=2*n-1;//数组共2n-1个元素
卢卡斯数列
HT=new HTNode[m+1];//0号单元未⽤，H[T]表⽰根结点
for(int i=1;i<m;i++)
{//将2n-1个元素的lch、rch、parent置为0
HT[i].lch=0;
HT[i].rch=0;
HT[i].parent=0;
}
for(int i=1;i<=n;i++)
{
cin>>HT[i].weight;//输⼊前n个元素的weight值
}
//初始化结束，下⾯开始建⽴哈夫曼树
for(int i=n+1;i<=m;i++)// 合并产⽣n-1个结点—构造哈夫曼树
{//通过n-1次选择、删除、合并来创建哈夫曼树
Select(HT,i-1,s1,s2);
//在HT[k](k>=1&&k<=i-1)中选择两个其双亲域为0
/
/且权值最⼩的结点，并返回它们在HT中的序号s1,s2；
HT[s1].parent=i;//将s1,s2的双亲域由0改为1
HT[s2].parent=i;//得到新结点i，从森林中删除s1,s2；
HT[i].lch=s1;
HT[i].rch=s2;//s1,s2分别作为i的左右孩⼦
HT[i].weight=HT[s1].weight+HT[s2].weight;
//i的权值为左右孩⼦权值之和
}
}
四、哈夫曼编码
前缀编码：如果在⼀个编码⽅案中，任⼀个编码都不是其他任何编码的前缀（最左⼦串），则称为前缀编码
问题引⼊：什么样的前缀编码能使电⽂总长最短？
——哈夫曼编码
⽅法：
1、统计字符集中每个字符在电⽂中出现的平均概率（概率越⼤，要求编码越短）。
2、利⽤哈夫曼树的特点：权越⼤的叶⼦离根越近；将每个字符的概率值作为权值，构造哈夫曼树，则概率越⼤的结点，路径越短。氯化铯
3、在哈夫曼树的每个分⽀上标上0或1：
结点的左分⽀标0，右分⽀标1
把从根到每个叶⼦的路径上的标号连接起来，作为该叶⼦代表的字符的编码。
所以哈夫曼编码就是
对⼀颗具有n个叶⼦的哈夫曼树，若对树中的每个左分⽀赋予0，右分⽀赋予1，则从根到每个叶⼦的路径上，各分⽀的赋值分别构成⼀个⼆进制串，该⼆进制串就称为哈夫曼编码。
下⾯看两个问题：
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议