树和二叉树(5哈夫曼树及其应用)【优质课堂】

1、6.6哈夫曼树及其应用,1,优质课堂,1.相关概念 路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。 如结点A到结点F的路径为： A-B-E-F,A,B,C,D,E,F,G,6.6.1最优二叉树,2,优质课堂,路径长度：路径上面的分支个数。 如A-F的路径长度为3。,A,B,C,D,E,F,G,3,优质课堂,树的路径长度：从树根到每一个结点的路径长度之和。 如左边树的路径长度为： Len(A-B)+ Len(A-C)+ Len(A-D)+ Len(A-E)+ Len(A-F)+ Len(A-G) =1+1+2+2+3+3=12,A,B,C,D,E,F,G,4,优质课堂,结点的权

2、值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。 如左图。,A,B,C,D,E,F,G,4,1,2,5,3,7,5,优质课堂,结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘积。 如结点E的带权路径长度为:Len(E-A)*3=2*3=6,A,B,C,D,E,F,G,4,1,2,5,3,7,6,优质课堂,树的带权路径长度： 树中所有叶子结点的带权路径长度之和。 记作： WPL=w1*L1+w2*L2+wn*Ln,A,B,C,D,E,F,G,w1,w2,w3,w4,7,优质课堂,最优二叉树（哈夫曼树）：给定n个权值w1,w2,wn，试构

3、造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。构造出来的二叉树的形态可以有多个，我们把其中带权路径长度WPL最小的二叉树称作最优二叉树或者哈夫曼树。,A,B,C,D,E,F,G,w1,w2,w3,w4,8,优质课堂,2.哈夫曼算法,（1） 如何构造一棵哈夫曼树。 我们首先通过一个例子来演示一下构造过程。,9,优质课堂,当权值为7，5，2，4时，构造哈夫曼树。,7,5,2,4,10,优质课堂,当权值为7，5，2，4时，构造哈夫曼树。,7,5,2,4,6,11,优质课堂,当权值为7，5，2，4时，构造哈夫曼树。,7,2,4,6,5,12,优质课堂,当权值为7，5，2，4时，构造哈夫曼树。,

4、7,2,4,6,5,11,13,优质课堂,当权值为7，5，2，4时，构造哈夫曼树。,7,2,4,6,5,11,14,优质课堂,当权值为7，5，2，4时，构造哈夫曼树。,7,2,4,6,5,11,18,15,优质课堂,（2）哈夫曼算法的语言描述,根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 在F中删除这两棵树，同时将新得到的二叉树加入F中。 重复和，直到F只含一棵树为止。这棵

5、树便是哈夫曼树。,16,优质课堂,6.6.2 哈夫曼编码,对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。 现在要对字符串进行0、1编码，有哪些方法？哪一种编码的长度最短？,17,优质课堂,1.各种编码方式,（1）定长编码-根据出现的字符种数进行编码 字符串“ABACCDA”中共出现4种字符，那么可以用2位表示。,那么字符串“ABACCDA”的编码将为“00010010101100”，总长度为7*2=14位,18,优质课堂,1.各种编码方式,（1）定长编码-根据出现的字符种数进行编码 这种编码方式可以对应到二叉树，如右图所式,A,B,C,

6、D,0,0,0,1,1,1,19,优质课堂,1.各种编码方式,（2）变长编码 当A、B、C、D按照如下形式进行编码时。,那么字符串“ABACCDA”的编码将为“0110010101110”，总长度为13位，比第二种方式又要短。 采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。否则就会出现二义性。,20,优质课堂,1.各种编码方式,（2）变长编码 这种编码方式也可以对应到二叉树，如右图所式,A,B,C,0,0,1,1,D,0,1,21,优质课堂,1.各种编码方式,（2）变长编码 如当A、B、C、D按照如下形式进行编码时。,请将“0111”翻译成字符串。试

7、一试，有哪些翻译方式。 之所以会出现二义性，是因为出现了A的编码是C的编码的前缀； B的编码是D的编码的前缀.,22,优质课堂,1.各种编码方式,（2）变长编码 这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图,A,C,B,0,1,1,1,D,1,23,优质课堂,1.各种编码方式,从上面的分析可以看出，一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。 也可以看出，每一个可用的编码都可以转化成二叉树的形式，这样编码理论便可以与二叉树的一些性质结合起来，就可以应用二叉树的理论知识来解决编码问题。,24,优质课堂,1.各种编码方式,（3）哈夫曼编码

8、假设编码过程中有以下对应关系：,那么总的编码长度为： WPL=w1*L1+w2*L2+w3*L3+w4*L4 那么如何选择L1、L2、L3、L4的值，使得WPL最小呢？,25,优质课堂,1.各种编码方式,（3）哈夫曼编码,可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。,26,优质课堂,对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树,1,2,3,1,A,B,C,D,27,优质课堂,对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出

9、现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树,3,2,1,1,B,D,C,A,28,优质课堂,对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树,3,2,1,1,B,D,C,A,2,29,优质课堂,对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树,3,2,1,1,B,D,C,A,2,30,优质课堂,对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、

10、2、1。根据权值3，1，2，1 构造哈夫曼树,3,2,1,1,B,D,C,A,2,4,31,优质课堂,对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树,3,2,1,1,B,D,C,A,2,4,32,优质课堂,对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树,3,2,1,1,B,D,C,A,2,4,7,33,优质课堂,下面对哈夫曼树进行编码，每一个结点的左分支上面标0，右分支上面标1。,3,2,1,1,B,D,C,

11、A,2,4,7,34,优质课堂,下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。,3,2,1,1,B,D,C,A,2,4,7,0,35,优质课堂,下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。,3,2,1,1,B,D,C,A,2,4,7,0,1,36,优质课堂,下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。,3,2,1,1,B,D,C,A,2,4,7,0,1,0,37,优质课堂,下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。,3,2,1,1,B,D,C,A,2,4,7,0,1,0,1,38,优质课堂,下面对哈

12、夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。,3,2,1,1,B,D,C,A,2,4,7,0,1,0,1,0,39,优质课堂,下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,40,优质课堂,从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,41,优质课堂,从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。,3,2,1,1,B,D,C,A,2,4,7,1,0,

13、1,0,1,0,A：0,42,优质课堂,从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,A：0 B：1,43,优质课堂,从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。,A：0 B：11,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,44,优质课堂,从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。,A：0 B：110,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,45,优质课堂,从

14、根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。,A：0 B：110 C：1,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,46,优质课堂,从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。,A：0 B：110 C：10,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,47,优质课堂,从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。,A：0 B：110 C：10 D：1,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,48,优质课堂,从

15、根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。,A：0 B：110 C：10 D：11,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,49,优质课堂,从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。,A：1 B：110 C：10 D：111,3,2,1,1,B,D,C,A,2,4,7,1,0,1,0,1,0,50,优质课堂,思考,N个权值构造的哈夫曼树，树中结点总数是多少？ 哈夫曼树中，权值越大的结点越靠近根结点。该论断是否正确？,51,优质课堂,2.哈夫曼编码的具体实现,输入字符及其权重 根据权重构造哈

16、夫曼树 根据哈夫曼树编码,52,优质课堂,算法6.12的动态演示,（1）存储结构的选择 权值分别如下：,这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。采用双亲孩子表示法来存储哈夫曼树。,53,优质课堂,（2）初始化,54,优质课堂,55,优质课堂,(3)建树过程,56,优质课堂,第一步,57,优质课堂,58,优质课堂,59,优质课堂,60,优质课堂,61,优质课堂,62,优质课堂,第 二 步,63,优质课堂,64,优质课堂,65,优质课堂,66,优质课堂,67,优质课堂,68,优质课堂,第 三 步,69,优质课堂,70,优质课堂,71,优质课堂,72,优质课堂,73,

17、优质课堂,74,优质课堂,第 四 步,75,优质课堂,76,优质课堂,77,优质课堂,78,优质课堂,79,优质课堂,80,优质课堂,第 五 步,81,优质课堂,82,优质课堂,83,优质课堂,84,优质课堂,85,优质课堂,86,优质课堂,第 六 步,87,优质课堂,88,优质课堂,89,优质课堂,90,优质课堂,91,优质课堂,92,优质课堂,第 七 步,93,优质课堂,94,优质课堂,95,优质课堂,96,优质课堂,97,优质课堂,98,优质课堂,（4）编码过程,从叶子结点开始，向根回溯，来对叶子结点所代表的字符进行编码。,99,优质课堂,100,优质课堂,以第一个叶子结点为例：,1的双亲结点为9，且1是9的左孩子，故分支应该标“0”，所以编码“0”入栈。,101,优质课堂,以第一个叶子结点为例：,0,102,优质课堂,以第一个叶子结点为例：,9的双亲结点为11，且9是11的右孩子，故分支应该标“1”，所以编码“1”入栈。,0,103,优质课堂,以第一个叶子结点为例：,0,1,104,优质课堂,以第一个叶子结点为例：,11的双亲结点为13，且11是13的右孩子，故分支应该标“1”，所以编码“1”入栈。,0,1,105,优质课堂,以第一个叶子结点为例：,0,1,1,106,优质课堂,以第一个叶子结点为