6.6 Huffman树及其应用 王 玲.

Presentation on theme: "6.6 Huffman树及其应用 王 玲."— Presentation transcript:

1 6.6 Huffman树及其应用 王 玲

2 教学内容 远程通信中的一个问题 1 最优二叉树——Huffman树 2 Huffman编码及其实现 3 《数据结构》

3 远程通信中的一个问题 信道 设有一段信息（报文）需要编码传输： CASTCASTSATEATATASA
发送端（编码） 对 接收端（解码） … CASTCASTSATEATATASA 《数据结构》

4 解决方案1 等长编码： CASTCASTSATEATATASA A : 000, C :001, E:010, S :011, T :100 信息编码如下： 总编码长度为：( ) * 3 = 57（bits） 《数据结构》

5 解决方案2 不等长编码，例如： A : 0, C :1, E:10, S :11, T :100 信息编码如下（34bits）： 出现了二义问题。 采用前缀码。 Huffman编码是最优前缀码，要借助Huffman 树来完成编码和解码。 《数据结构》

6 最优二叉树——Huffman树 带权路径长度WPL达到最小的二叉树即为Huffman树（最优二叉树）。 1. 结点的路径长度
1. 结点的路径长度 2. 树的路径长度：树中结点的路径长度之和 3．结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 4．树的带权路径长度（WPL） 树的带权路径长度规定为所有叶子结点的带权路径长度之和。 《数据结构》

7 √ 最优二叉树——Huffman树 2 4 7 5 (b) 7 5 2 4 (c) 7 5 4 (a) 2
最优二叉树(Huffman树）：给定n个权值{w1,w2,…，wn},构造一棵有n个结点的二叉树，使每个叶结点带权为wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树。 2 4 7 5 (b) 7 5 2 4 (c) 7 5 4 (a) 2 √ 《数据结构》

8 Huffman树的一个实例 最佳判定树 考试成绩分布表 《数据结构》

9 Huffman树的一个实例 <60? <70? <80? <90? 0.10 0.15 0.25 0.35 <
不及格 及格 中 良 优 <60? <70? <80? <90? 0.10 0.15 0.25 0.35 ≥ < WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4 = 3.15 对10000个成绩，则总共需要31500次比较。 《数据结构》

10 Huffman树的一个实例 <60? <70? <80? <90? 0.10 0.15 0.25 0.35 <
不及格 及格 中 良 优 <60? <70? <80? <90? 0.10 0.15 0.25 0.35 ≥ < WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2 = = 2.25 对10000个成绩，则总共需要22500次比较。 《数据结构》

11 Huffman树的构造思路 选择 合并 初始化
根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1，T2，…，Tn),其中每棵二叉树Ti中只有一个带权为wi的根结点,左右子树为空。 在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。 在F中删除这两棵树，同时将新得到的二叉树加入F中。 重复，直到F中只含一棵树为止。这棵树就是Huffman树。 《数据结构》

12 以{7，2，1，4，5}为权值集合构造Huffman树。
（1） 4 2 5 7 1 2 1 3 7 4 5 12 （4） 2 1 3 （2） 4 5 7 2 1 3 7 4 5 12 （5） 19 （3） 2 1 3 5 4 7 12 《数据结构》

13 练习： 以｛ 9, 3, 7, 6, 12 , 5｝为权值构造一棵Huffman树，并计算它的WPL。 13

14 Huffman编码及其实现 C E 3 A S T 7 12 19 回到最初的问题，传输： CASTCASTSATEATATASA A：7
4 5 《数据结构》

15 Huffman编码及其实现 C E 3 A S T 7 12 19 将Huffman树的左子树置0，右子树置1，这样每个叶子都获得一个码字：
1 2 4 5 WPL=7×1+5×2+2×4+1×4+4×3=41 这里的WPL就是编码的总长度。 《数据结构》

16 解码算法： C E 3 A S T 7 12 19 1 2 4 5 CASTCASTSATEATATASA 《数据结构》

17 Huffman编码算法实现 weight parent lchild rchild
1.有n个叶结点的Huffman树中共有m＝2n－1个结点，可将这些结点存储在一个一维数组中。 weight parent lchild rchild 结点结构 typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; 2.可以采用动态分配的一维数组存储编码表。 typedef char ** HuffmanCode; 17 《数据结构》

18 1 7 2 5 3 4 - 6 例：以{7，5，2，4}为权值集合构造哈夫曼树。 2 4 5 7 weight parent lchild
rchild 1 7 2 5 3 4 - 6 例：以{7，5，2，4}为权值集合构造哈夫曼树。 （1） 2 4 5 7 1 3 18

19 weight parent lchild rchild 1 7 2 5 3 4 6 - （2） 2 4 5 7 6 1 3 19

20 weight parent lchild rchild 1 7 2 5 6 3 4 11 - （3） 2 4 5 7 6 11 1 3 20

21 7 5 6 11 18 1 2 3 4 2 4 5 7 6 11 18 weight parent lchild rchild （4） 1
2 5 6 3 4 11 18 （4） 2 4 5 7 6 11 18 1 3 21

22 权值={ 5, 29, 7, 8, 14, 23, 3, 11 } weight parent lchild rchild 1 5 2 29 3 7 4 8 14 6 23 11 9 - 10 12 13 15 1.HT的初态 5 1 29 2 7 3 8 4 23 6 11 14

23 i = n+1 = 9 在前 i -1 = 8 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 7 s2 = 1
构造新结点，存储于 下标为 i = 9 的元素中 权值=最小及次小权和 = = 8 构造以元素9为根的子 二叉树 index weight parent lchild rchild 1 5 2 29 3 7 4 8 14 6 23 11 9 10 12 13 15 9 8 7 1 2019/2/15

24 i + 1 = 10 在前 i -1 = 9 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 3 s2 = 4
新结点存储于元素10 权值 = = 15 构造元素10的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 6 23 11 15 12 13 2019/2/15

25 i + 1= 11 在前 i -1 = 10 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 9 s2 = 8
新结点存储于元素11 权值 = = 19 构造元素11的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 6 23 11 15 19 12 13 2019/2/15

26 i + 1 = 12 在前 i -1 = 11 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 5 s2 = 10
新结点存储于元素12 权值 = = 29 构造元素12的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 12 6 23 11 15 19 13 2019/2/15

27 i + 1= 13 在前 i -1 = 12 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 11 s2 = 6
新结点存储于元素13 权值 = = 42 构造元素13的子二叉树 no weight parent lchild rchild 1 5 9 2 29 3 7 10 4 8 14 12 6 23 13 11 15 19 42 2019/2/15

28 i + 1 = 14 在前 i -1 = 13 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 2 s2 = 12
新结点存储于元素14 权值 = = 58 构造元素14的子二叉树 no weight parent lchild rchild 1 5 9 2 29 14 3 7 10 4 8 12 6 23 13 11 15 19 42 58 2019/2/15

29 i + 1 = 15 在前 i -1 = 14 个元素中 找无父结点且有最小及 次小权值元素的下标 s1 = 13 s2 = 14
新结点存储于元素15 权值 = = 100 构造元素15的子二叉树 no weight parent lchild rchild 1 5 9 2 29 14 3 7 10 4 8 12 6 23 13 11 15 19 42 58 100 2019/2/15

30 2.HT的终态 5 3 14 8 11 15 29 58 19 42 23 100 weight parent lchild rchild
2 29 14 3 7 10 4 8 12 6 23 13 11 15 19 42 58 100 2.HT的终态 5 1 3 7 14 8 4 11 9 15 10 29 2 12 58 19 42 13 23 6 100

31 int Huffman( HuffmanTree HT, int *w , int n ) {
for( i = 1 ; i < 2*n ;i++) { // 初始化 HT[i].parent = HT[i].lchild = HT[i].rchild = 0; if (i <= n) HT[i].weight = w[i-1]; // 前 n 个结点赋权值 else HT[i].weight = 0; // 后 n-1 个结点预留 } //初始化结束 // 待续… 2019/2/15

32 int Huffman( HuffmanTree HT, int *w , int n ) { // …续
for ( i = n+1 ; i <=2*n-1 ; i++) { // 构造 HUFFMAN树 Select ( HT , i - 1 , &s1, &s2 ) ; // 最小及次小权元下标 HT[s1].parent = i; // 设置新根结点 HT[s2].parent = i; HT[i].weight = HT[s1].weight + HT[s2].weight ; // 权值和 HT[i].lchild = s1; // 根结点与子结点链接 HT[i].rchild = s2; } //结束构造 } 2019/2/15

33 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w[ ],int n){ if ( n<=1) return 0; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for (i=1;i<=m;i++) if (i<=n) HT[i]={w[i],0,0,0}; else HT[i]={0,0,0,0}; for (i=n+1;i<=m;i++) {//建立Huffman树 Select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight= HT[s1].weight+ HT[s2].weight; } 33

34 //求叶到根逆向求每个字符的Huffman编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]=‘\0’; for (i=1;i<=n;i++) {start=n-1; for (c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if (HT[f].lchild==c) cd[- -start]=‘0’; else cd[--start]=‘1’; HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); }//HuffmanCoding 34

35 算法 Huffman译码 void HuffmandeCoding(HuffmanTree HT,int n){ m=2*n-1; i=m;
while ((ch=getchar())!=‘\n’){ if (i<=n){ printf(HT[i].data); i=m;} if (ch==‘0’) i=HT[i].lchild; else i=HT[i].rchild; }//while }// HuffmandeCoding 35

36 小结 问题1 Huffman树的不唯一性是否会影响到Huffman编码？ 问题3 方法能否扩展到k元Huffman编码？ 问题2
《数据结构》

37 本章小结 第6章结束 树 森林 先、后根遍历 层次遍历 孩子--兄弟 存储结构 遍历 1.定义和性质 顺序结构 2.存储结构 二叉链表
二叉树 森林 顺序结构 链式结构 2.存储结构 二叉链表 三叉链表 中序遍历 后序遍历 先序遍历 层次遍历 3.遍历 遍历 Huffman树 应用 要求熟悉树和二叉树的定义和有关术语； 理解和记住二叉树的性质； 熟练掌握二叉树的顺序存储结构和链式存储结构。 遍历二叉树是二叉树中各种运算的基础，希望能灵活运用各种次序的遍历算法，实现二叉树的其他运算。 二叉树的线索化，目的是加速遍历过程和有效利用存储空间，希望熟练掌握。 并能掌握： 树和二叉树之间的转换方法，存储树的双亲表示法、孩子表示法和孩子兄弟法。 最后，对树和森林的遍历、最优二叉树的特性，建议读者要理解。 先序线索树 中序线索树 后序线索树 先 序 遍 历 中 4.线索化 线索二叉树 Huffman编码

38 习题 一、判断题 1.二叉树是树的特殊形式。 2.一棵度为2的树就是一棵二叉树。 3.由树转换成二叉树，其根结点的右子树总是空的。
4.如果结点A有3个兄弟，而且B是A的双亲，则B的度是5。 5.给定二叉树的先序遍历序列和后序遍历序列，就能惟一地确定一棵二叉树。 6.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

39 二、填空题 1.对于一个具有n个结点的二叉树，当它为一棵_________二叉树时，具有最小高度，即为_________，当它为一棵单支树时具有具有最大高度，即为_________。 2.对于一个具有n个结点的二叉树，当它存储在二叉链表中时，其指针字段的总数为_________个，其中_________个用于链接孩子结点，_________个空闲。 3.一棵深度为k的满二叉树的结点总数为___________，一棵深度为k的完全二叉树的结点总数的最小值为___________，最大值为___________。 4. 由三个结点构成的二叉树，共有_________种不同的结构。

40 5. 设深度为k的二叉树上只有度为0或度为2的结点，则这类二叉树上所含结点总数至少为_____。
6.具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号(根结点为1号)，则编号最大的分支结点序号为_______，编号最小的分支结点序号为_______，编号最大的叶子结点序号为________，编号最小的叶子结点序号为________。 7.有m个叶子结点的哈夫曼树，其结点总数为_______。 8.某二叉树的前序遍历结点访问顺序为ABDGCEFH，中序遍历结点访问顺序为DGBAECHF，则其后序遍历结点访问顺序为_____。

41 三、 简答题 1. 遍历序列具有如下特点的二叉树具有什么特征？（注意：二叉树至少有两个结点） 先序序列和后序序列正好相反
三、 简答题 1. 遍历序列具有如下特点的二叉树具有什么特征？（注意：二叉树至少有两个结点） 先序序列和后序序列正好相反 先序序列和中序序列正好一致 中序序列和后序序列正好一致 中序序列是一个有序序列 2.具有3个结点的树和3个结点的二叉树的有多少种不同形态，请分别画出来。

42 3. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树。
4.对于权值W＝{14，15，7，4，20，3}，试给出相应的哈夫曼树，并计算其带权长度。

43 Click to edit company slogan .
Thank You ! Click to edit company slogan .