2011年10月 计算机科学与工程学院 TCS.CQ 第 4 页
哈夫曼树构造算法
1、给定一个具有n个权值{ w1,w2,………wn }的结点的集合
F = { T1,T2,………Tn }
2、 初始时，设集合 A = F。 3、 执行 i = 1 至 n -1 的循环，在每次循环时执行以下操作
从当前集合中选取权值最小、次最小的两个结点，以这两个 结点作为内部结点 bi 的左右儿子，bi 的权值为其左右儿子 权值之和。 在集合中去除这两个权值最小、次最小的结点，并将内部结 点bI 加入其中。这样，在集合A中结点个数便减少了一个。
第 9 页
2011年10月
计算机科学与工程学院 TCS.CQ
a(10), e(15), i(12), s(3), t(4), 空格(13), 换行(1)。
a 10 a 10 e 15 e 15 i 12 i 12 S 3 t 4 t 4 空格 13 S 3 8 a 10 e 15 i 12 空格 13 S 3
计算机科学与工程学院 TCS.CQ
2 5 i 12 空格 13 5 8 4
3 3 1 8 8 t 4 换行 1 a 10 e 15
3 3
1 8 8 4 S 3 t 4 换行 1
2 5 e 15 i 12 空格 13
3
S
a 10
《数据结构》课件
计算机科学与工程学院 TCS.CQ
第 12 页
哈夫曼编码 A 001
2011年10月 计算机科学与工程学院 TCS.CQ 第 7 页
前缀编码
字符只放在叶结点中，所以任何一个字符的编码 都不是同一字符集中另一个字符的编码的前缀。 利用赫夫曼树可以构造一种不等长的二进制编码， 并且构造所得的赫夫曼编码是一种最优前缀编码， 即使所传电文的总长度最短。 字符编码可以有不同的长度
前缀编码可被惟一解码
《数据结构》课件
计算机科学与工程学院 TCS.CQ
第8页
哈夫曼树是一棵最小 代价的二叉树，在这 棵树上，所有的字符 都包含在叶结点上。
要使得整棵树的代价 最小，显然权值大的 叶子应当尽量靠近树 根，权值小的叶子可 以适当离树根远一些。
对应的哈夫曼编码如下： 1：000 3：001 5：01 7：1
这样，在经过了n-1 次循环之后，集合A中只剩下了一个结 点，这个结点就是根结点。
《数据结构》课件 计算机科学与工程学院 TCS.CQ 第5页
给定权值w=(1,3,5,7)来构造一棵哈夫曼树 。
16 4 1 3 5 7 1 3 1 (a) (b) 5 7 4 3 (c) 9 5 1 7 4 3 (d) 9 5 7
计算机科学与工程学院 TCS.CQ
第 16 页
赫夫曼树的存储
在哈夫曼树中，每个要编码的元素是一个叶结点，其它
结点都是度数为2的节点 一旦给定了要编码的元素个数，由n0＝n2＋1可知哈夫曼 树的大小为2n-1 哈夫曼树可用一个大小为2n的数组来存储。0节点不用， 根存放在节点1。叶结点依次放在n+1到2n的位置 每个数组元素保存的信息：结点的数据、权值和父结点
第 20 页
赫夫曼树的构造算法
void CreateHT(HTNode ht[],int n) { int i,j,k,lnode,rnode; for (i=0;i<2*n-1;i++) for (i=n;i<2*n-1;i++) { min1=min2=32767; for (k=0;k<=i-1;k++) if (ht[k].parent==0) { /*未构造二叉树的结点中查找或者=-1*/ lnode=rnode=0; float min1,min2; ht[i].parent=ht[i].lchild=ht[i].rchild=0; /*所有结点的相关域置初值或者-1*/
和左右孩子的位置
《数据结构》课件
计算机科学与工程学院 TCS.CQ
第 17 页
用ht[]数组存放哈夫曼树,对于具有n个叶子结点的哈夫 曼树,总共有2n-1个结点。 其算法思路是： n个叶子结点只有data和weight域值,先将所有2n-1个结点 的 parent 、 lchild 和 rchild 域置为初值 -1( 或者 0) 。处理每个 非叶子结点ht[i](存放在ht[n]～ht[2n-2]中)：从ht[0] ～ht[i-2] 中找出根结点 ( 即其 parent 域为 -1 或者为 0) 的最小的两个结 点 ht[lnode] 和 ht[rnode], 将 它 们 作 为 ht[i] 的 左 右 子 树,ht[lnode]和ht[rnode]的双亲结点置为ht[i],并且 ht[i].weight=ht[lnode].weight+ht[rnode].weight。 如此这样直到所有2n-1个非叶子结点处理完毕。
2011年10月
计算机科学与工程学院 TCS.CQ
第 21 页
根据哈夫曼树求对应的哈夫曼编码的算法如下：
void CreateHCode(HTNode ht[],HCode hcd[],int n) { int i,f,c; HCode hc; for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码*/
E 01
e i sp
I 10
S 00000 T 0001
a
t
Sp 11
Nl 00001
s
nl
总共用了146bit
《数据结构》课件 计算机科学与工程学院 TCS.CQ 第 13 页
题例: 已知权值 W={ 5, 6, 2, 9, 7 }
5 6
6 9
2 7
9 7
7
所有原始结点是有一个 根结点，五左右子树
hc.cd[hc.start--]='1'; c=f;f=ht[f].parent; } hc.start++; hcd[i]=hc; } /*start指向哈夫曼编码最开始字符*/ /*再对双亲结点进行同样的操作*/
}
2011年10月 计算机科学与工程学院 TCS.CQ 第 22 页
编码的产生
对每个结点，从叶子往根推进，是左枝加0，是右枝加1
构造一棵哈夫曼树的过程
2011年10月 计算机科学与工程学院 TCS.CQ 第 6 页
哈夫曼编码
具体构造方法如下：
设需要编码的字符集合为 {d1,d2,…,dn}, 各个字符在 电 文 中 出 现 的 次 数 集 合 为 {w1,w2,…,wn}, 以 d1,d2,…,dn作为叶结点 ,以 w1,w2,…,wn作为各根结点 到每个叶结点的权值构造一棵二叉树。规定哈夫曼 树中的左分支为0,右分支为1,则从根结点到每个叶结 点所经过的分支对应的 0和 1组成的序列便为该结点 对应字符的编码。 这样的编码称为哈夫曼编码。 哈夫曼编码的生成： 每个字符的编码是根节点到该 字符的路径；左枝为0，右枝为1
5 9
5
《数据结构》课件
2 13
7
2 6
7
第 14 页
计算机科学与工程学院 TCS.CQ
9
5
7
2 6
13
7 0 0 6 00 13 1 7 01 29 0 9 10 1 16 0 5 110 1
7
《数据结构》课件
计算机科学与工程学院 TCS.CQ
第 15 页
1 2 111
哈夫曼树结点的数据结构(类型)
值 权 父 左 右 2 3 58 33 25 18 8 1 4 8 1 9 2 5 4 6 4 5 10 a e i s t 4 5 sp nl 13 1 3 6 10 15 12 3 4 2 3 6
WPL
w l
i 1
n
i i
其中 ,n 表示叶子结点数 ,wi 和 li 分别表示叶子结点 ki 的权值 和根到 ki之间的路径长度 (即从叶结点到根结点的分支数 )。 具有最小带权路径长度的二叉树称为哈夫曼树，又称 之为最优二差树。
2011年10月 计算机科学与工程学院 TCS.CQ 第 2 页
{ hc.start=n;c=i; f=ht[i].parent;
while (f!=-1) { if (ht[f].lchild==c) /*循环直到无双亲结点即到达树根结点*/ /*当前结点是左孩子结点*/
hc.cd[hc.start--]='0';
else
/*当前结点是双亲结点的右孩子结点*/
/*构造哈夫曼树*/ /*或者-1*/
if (ht[k].weight<min1) { min2=min1; rnode=lnode; min1=ht[k].weight;lnode=k; }
else if (ht[k].weight<min2) { } /*if*/ ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; } } min2=ht[k].weight;rnode=k; }
生成过程分析
a e 15 2 i 12 3 s 3 6 t 4 5 sp 13 3 nl 1 6
3
值 权 父 左 右 0 2 3 1 58 33 1 4 8 2 25 1 9 12 3 18 2 5 7 4 8 4 6 11 5 4 5 10 13 6
10 4
7
8
9
10
11
12
13
《数据结构》课件
计算机科学与工程学院 TCS.CQ
《数据结构》课件 计算机科学与工程学院 TCS.CQ