树和二叉树（四）.

Presentation on theme: "树和二叉树（四）."— Presentation transcript:

1 树和二叉树（四）

2 内容回顾 树的存储方式 孩子兄弟表示法 树与二叉树的转换 树转二叉树 二叉树还原为树

3 本节内容 1 哈夫曼树的相关概念 2.哈夫曼树的构造算法 3.判定树 (哈夫曼树的应用之一) 4.哈夫曼编码（哈夫曼树的应用之二）
5.建立哈夫曼树及求哈夫曼编码的算法

4 1 哈夫曼树的相关概念 A B C D E F G 1）路径和路径长度 若一棵树中存在一个结点序列k1,k2,…,kj，使得ki是kj的双亲（0<i<j），则称此结点序列是从ki～ kj的路径。从k1～kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1。

5 2）结点的权和带权路径长度 例：结点c的路径长度为2，其WPL=2*9=18
在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，称其为该结点的权。 结点的带权路径长度（WPL)规定为从树根到该结点之间的路径长度与该结点上权的乘积。 例：结点c的路径长度为2，其WPL=2*9=18 a c b d 7 3 9 8

6 树中所有叶子结点的带权路径长度之和。通常记为：
3）树的带权路径长度 树中所有叶子结点的带权路径长度之和。通常记为： 其中 n 表示叶子结点的数目，wi 和 li分别表示叶子结点ki的权值和根到ki之间的路径长度。 a c b d 7 3 9 8

7 4）哈夫曼（Huffman）树 又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。 例：有四个叶子结点a,b,c,d，分别带权为9、4、5、2，由它们构成三棵不同的二叉树。

8 a b c a） WPL=9×2 +4×2＋5×2＋2×2＝40 b） WPL=4×1＋2×2＋5×3＋9×3＝50
d 4 9 5 2 b c d a 4 9 5 2 a b c d 9 2 4 5 a b c a） WPL=9×2 +4×2＋5×2＋2×2＝40 b） WPL=4×1＋2×2＋5×3＋9×3＝50 c） WPL=9×1＋5×2＋4×3＋2×3＝37 Huffman树

9 3) 从F中删去这两棵树，同时加入刚生成的新树； 4) 重复(2)和(3)两步，直至F中只含一棵树为止。
2.哈夫曼树的构造算法 构造Huffman树的基本思想： 权值大的结点用短路径，权值小的结点用长路径。 构造Huffman树的步骤（即Huffman算法）： 1）根据给定的n个权值{w1, w2, …, wn}，构造 n棵二叉树的集合 F = {T1, T2, …,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树； 2) 在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和; 3) 从F中删去这两棵树，同时加入刚生成的新树； 4) 重复(2)和(3)两步，直至F中只含一棵树为止。

10 第一步： 第二步： 第三步： 第四步： 注：方框表示外结点（叶子） 圆框表示内结点（合并后的结点）。 a b c d 9 2 5 4 a c
6 第二步： a b c d 9 2 4 5 第三步： 6 11 第四步： a 9 b c d 2 4 5 6 11 20 注：方框表示外结点（叶子） 圆框表示内结点（合并后的结点）。

11 3.判定树 (哈夫曼树的应用之一) 在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。 例：编制一将学生百分成绩按分数段分级的程序。
若学生成绩分布是 均匀的，可用图(a) 二叉树结构来实现。 a<60 a<70 a<80 a<90 不及格 中等 良好 优秀 及格 Y N (a)

12 学生成绩分布不是均匀的情况： 输入10000个数据，则需进行31500次比较。 分数 0—59 60—69 70—79 80—89
90—99 比例 0.05 0.15 0.4 0.3 0.1 a<60 a<70 a<80 a<90 不及格 中等 良好 优秀 及格 Y N (a) 输入10000个数据，则需进行31500次比较。 500*1+1500*2+4000*3+3000*4+1000*4=31500

13 有没有一种更好的办法来减少比较次数呢？

14 以比例数为权构造一棵哈夫曼树，如（b)判断树所示。
分数 0—59 60—69 70—79 80—89 90—99 比例 0.05 0.15 0.4 0.3 0.1 70≤a<80 a<60 及格 中等 良好 80≤a<90 60≤a<70 不及格 优秀 Y N 以比例数为权构造一棵哈夫曼树，如（b)判断树所示。 再将每一比较框的两次比较改为一次，可得到（c)判定树。 输入10000个数据，仅需进行22000次比较。 不及格 Y a<90 a<80 a<70 a<60 优秀 中等 及格 良好 N (c) (b)

15 4.哈夫曼编码（哈夫曼树的应用之二） 1）二进制编码 通信中，可以采用0、1的不同排列来表示不同的字符，称为二进制编码。
发送端需要将电文中的字符序列转换成二进制的0、1序列，即编码； 接受端需要把接受的0、1序列转换成对应的字符序列，即译码。

16 字符：A B A C C D A A B C D的编码分别为：00、01、10、11 电文： 电文总长度为：14

17 如何能缩短传送电文的 总长度，从而节省传送 时间呢？

18 ? 若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样有可能缩短传送电文的总长度。
字符：A B A C C D A A B C D的编码分别为：0、00、1、01 电文： 电文总长度为：9 ? 无法译码！为此引入前缀编码的概念

19 2）前缀编码 若对某一字符集进行不等长编码，则要求字符集中任一字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。 如何设计前缀编码？

20 如何得到电文总长最短的二进制前缀编码呢？
利用二叉树设计二进制的前缀编码 假设有一棵如左图所示的二叉树，四个叶结点分别表示A、B、C、D四个字符，且约定左分支表示字符‘0’，右分支表示字符‘1’，则可以从根结点到叶子结点的路径上以分支字符组成的字符串作为该叶子结点的编码。可以证明，如此得到的必为二进制前缀编码。 1 a b c d 1 如何得到电文总长最短的二进制前缀编码呢？

21 3）哈夫曼编码 设计电文总长最短的二进制前缀编码即： 以 n种字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码称哈夫曼编码。

22 哈夫曼编码的基本思想是：概率大的字符用短码，概率小的用长码。由于哈夫曼树的WPL最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。
例：假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}，试为这8个字母设计赫夫曼编码。如果用0～7的二进制编码方案又如何？ 解：先将概率放大100倍，以方便构造赫夫曼树。 权值集合 w={7, 19, 2, 6, 32, 3, 21, 10}， 按赫夫曼树构造规则（合并、删除、替换），可得到赫夫曼树。

23 为清晰起见，重新排序为: w={2, 3, 6, 7, 10, 19, 21, 32} × w1={5, 6, 7, 10, 19, 21, 32} × 100 w2={7, 10, 11, 19, 21, 32} × w3={11, 17, 19, 21, 32} × 21 19 40 32 60 w4={19, 21, 28, 32} × 28 w5={28,32,40} × g e b w6={40,60} × 17 11 10 7 w7={100} 6 2 3 5 a d 赫夫曼树 h c f

24 对应的哈夫曼编码（左0右1）： 5 6 11 10 7 32 17 28 21 19 40 60 b a d e g 1 2 3 h c f
100 b a d e g 1 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 1100 00 11110 1110 10 11111 01 1101 000 001 010 011 100 101 110 111 2 3 h c f Huffman码的WPL＝2( ) + 4( ) +5( ) = =2.61 WPL＝3( )=3 二进制码

25 5.建立哈夫曼树及求哈夫曼编码的算法 哈夫曼树没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。 由于在构造哈夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。所以，每个结点既需知道双亲的信息，又需知道孩子结点的信息。 typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; } HTNode, *HuffmanTree; //动态分配数组存储哈夫曼树 typedef char **HuffmanCode;

26 //存放树的叶子结点，n-1个单元存放内部结点 for (p=HT, i=1; i<=n; ++i,++p,++w)
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w, int n) {//w存放n个字符的权值，构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC if (n<=1) return; // n为字符数目， m=2*n-1; // m为结点数目 HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //HT存放Huffman树结构，0号单元未用,其余前n个单元 //存放树的叶子结点，n-1个单元存放内部结点 for (p=HT, i=1; i<=n; ++i,++p,++w) { p->weight = *w; p->parent=0; p->lchild=0; p->rchild=0; } // *p={*w,0,0,0}；初始化HT中的叶结点循环退出时i=n+1;

27 for (; i<=m;++i,++p)
{ p->weight = 0; p->parent=0; p->lchild=0; p->rchild=0; } // *p={0,0,0,0}; 初始化HT中的内部结点 for (i=n+1; i<=m;++i) // 建哈夫曼树，(建立HT静态链表中的链) { Select(HT,i-1,s1,s2);//在HT[1～i-1]中选择parent // 为0且weight最小的两个结点，序号分别为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; }

28 //从叶子到根逆向求哈夫曼编码 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[c].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]); //从cd复制编码串到HC printf("%s\n",HC[i]); } free(cd); //释放工作空间 } //HuffanCoding

29 设权w=（5，29，7，8，14，23，3，11），n=8，则m=15 存储结构的初始状态为：
例： 已知某系统在通信联络中只可能出现八种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计Huffman编码。 设权w=（5，29，7，8，14，23，3，11），n=8，则m=15 存储结构的初始状态为： 11 3 23 14 8 7 29 5 weight parent lchild rchild 1 2 4 6 9 10 12 13 15 14 13 100 12 2 0(15) 58 11 6 42 10 5 0(14) 29 9 8 0(13) 19 × 4 3 0(12) 15 × 7 1 0(11) 8 × 11 × 0(9) 3 × 23 × 14 × 0(10) 7 × 5× weight parent lchild rchild 15

30 HC 1 2 3 4 5 6 7 8 1 0 0 0 1 1 1 23 29 1 1 11 14 1 1 5 3 7 8 cd \0

31 小结：哈夫曼树及其应用 1.Huffman算法的思路： —权值大的结点用短路径，权值小的结点用长路径。

32 二叉树小结 1、定义和性质 2、存储结构 3、遍历 树 顺序结构 链式结构 森林 先序遍历 中序遍历 后序遍历 赫夫曼树 赫夫曼编码
二叉链表 三叉链表 森林 二叉树 中序遍历 后序遍历 先序遍历 3、遍历 赫夫曼树 赫夫曼编码

33 本章小结 1、定义和性质 2、存储结构 3、遍历 树 顺序结构 链式结构 森林 先序遍历 中序遍历 后序遍历 哈夫曼树 哈夫曼编码 二叉链表
三叉链表 森林 二叉树 中序遍历 后序遍历 先序遍历 3、遍历 哈夫曼树 哈夫曼编码

34 作业 1. 以数据集{4，5，6，7，10，12，18}为结点权值，画出Huffman树，并计算其带权路径长度。