1、树和二叉树哈夫曼树及其应用1.相关概念路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。如结点A到结点F的路径为：A-B-E-FABCDEFG路径长度：路径上面的分支个数。如A-F的路径长度为3。ABCDEFG树的路径长度：从树根到每一个结点的路径长度之和。如左边树的路径长度为：Len(A-B)+Len(A-C)+Len(A-D)+Len(A-E)+Len(A-F)+Len(A-G)=1+1+2+2+3+3=12ABCDEFG结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。如左图。ABCDEFG412537结点的带权路径长度
2、：该结点到根结点的路径长度与该结点上权的乘积。如结点E的带权路径长度为:Len(E-A)*3=2*3=6ABCDEFG412537树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作：WPL=w1*L1+w2*L2+wn*LnABCDEFGw1w2w3w4从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。这种编码方式也可以对应到二叉树，如右图所式这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图当A、B、C、D按照如下形式进行编码时。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。当A
3、、B、C、D按照如下形式进行编码时。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。其中A、B、C、D出现的次数分别为3、1、2、1。重复和，直到F只含一棵树为止。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。15的双亲结点为0，所以可以判断15就是根结点，那么第一个结点编码完毕，编码应该从栈顶向栈底读，为“0110”。这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图以第一个叶子结点为例：从根结点到各个叶子结点
4、，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。9的双亲结点为11，且9是11的右孩子，故分支应该标“1”，所以编码“1”入栈。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。最优二叉树（哈夫曼树）：给定n个权值w1,w2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。构造出来的二叉树的形态可以有多个，我们把其中带权路径长度WPL最小的二叉树称作最优二叉树或者哈夫曼树。AB
5、CDEFGw1w2w3w42.哈夫曼算法（1）如何构造一棵哈夫曼树。我们首先通过一个例子来演示一下构造过程。当权值为7，5，2，4时，构造哈夫曼树。7524从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。对于字符串“ABACCDA”，共有7个字符，4种字符。从叶子结点开始，向根回溯，来对叶子结点所代表的字符进行编码。（2）哈夫曼算法的语言描述如左边树的路径长度为：这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图11的双亲结点为13，且11是13的右孩子，故分支应该标“1”，所以编码“1”入栈。以第一个叶子结点为例：13的
6、双亲结点为15，且13是15的左孩子，故分支应该标“0”，所以编码“0”入栈。也可以看出，每一个可用的编码都可以转化成二叉树的形式，这样编码理论便可以与二叉树的一些性质结合起来，就可以应用二叉树的理论知识来解决编码问题。这种编码方式也可以对应到二叉树，如右图所式以第一个叶子结点为例：下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。以第一个叶子结点为例：当权值为7，5，2，4时，构造哈夫曼树。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。对于字符串“ABACCDA”，共有7个字符，4种字符。当权值为7，5，2，4时，构造哈夫曼树。根据权值3，1，2，1
7、构造哈夫曼树路径长度：路径上面的分支个数。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图当权值为7，5，2，4时，构造哈夫曼树。75246当权值为7，5，2，4时，构造哈夫曼树。72465当权值为7，5，2，4时，构造哈夫曼树。7246511当权值为7，5，2，4时，构造哈夫曼树。7246511当权值为7，5，2，4时，构造哈夫曼树。724651118（2）哈夫曼算法的语言描述根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树Ti中
8、只有一个带权为wi的根结点，其左右子树为空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复和，直到F只含一棵树为止。这棵树便是哈夫曼树。对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。现在要对字符串进行0、1编码，有哪些方法？哪一种编码的长度最短？1.各种编码方式（1）定长编码-根据出现的字符种数进行编码字符串“ABACCDA”中共出现4种字符，那么可以用2位表示。ABCD000110111.各种编码方式（
9、1）定长编码-根据出现的字符种数进行编码这种编码方式可以对应到二叉树，如右图所式ABCD00011011ABCD0001111.各种编码方式（2）变长编码当A、B、C、D按照如下形式进行编码时。ABCD011010111 采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。否则就会出现二义性。1.各种编码方式（2）变长编码这种编码方式也可以对应到二叉树，如右图所式ABCD011010111ABC0011D01N个权值构造的哈夫曼树，树中结点总数是多少？下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。重复和，直到F只含一棵树为止。从根结点
10、到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图如结点E的带权路径长度为:Len(E-A)*3=2*3=6以第一个叶子结点为例：WPL=w1*L1+w2*L2+w3*L3+w4*L4当A、B、C、D按照如下形式进行编码时。以第一个叶子结点为例：哈夫曼树中，权值越大的结点越靠近根结点。Len(A-B)+Len(A-C)+Len(A-D)+Len(A-E)+Len(A-F)+Len(A-G)如结点E的带权路径长度为:Len(E-A)*3=2*3=6可以看出，该公式与哈夫曼树满足的公式一
11、模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。其中A、B、C、D出现的次数分别为3、1、2、1。那么总的编码长度为：从上面的分析可以看出，一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。其中A、B、C、D出现的次数分别为3、1、2、1。1.各种编码方式（2）变
12、长编码如当A、B、C、D按照如下形式进行编码时。ABCD01101111 请将“0111”翻译成字符串。试一试，有哪些翻译方式。之所以会出现二义性，是因为出现了A的编码是C的编码的前缀；B的编码是D的编码的前缀.1.各种编码方式（2）变长编码这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图ABCD01101111ACB0111D11.各种编码方式从上面的分析可以看出，一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。也可以看出，每一个可用的编码都可以转化成二叉树的形式，这样编码理论便可以与二叉树的一些性质结合起来，就可以应用二叉树的理论知识来解决
13、编码问题。1.各种编码方式（3）哈夫曼编码假设编码过程中有以下对应关系：字符ABCD权重（字符出现次数）w1 w2 w3 w4编码长度L1L2L3L4 那么总的编码长度为：WPL=w1*L1+w2*L2+w3*L3+w4*L4 那么如何选择L1、L2、L3、L4的值，使得WPL最小呢？1.各种编码方式（3）哈夫曼编码可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树1231ABCD 对于字符串“ABACCDA”
14、，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树3211BDCA 对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树3211BDCA2 对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树3211BDCA2 对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树3211B
15、DCA24 对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树3211BDCA24 对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树3211BDCA247根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。以第一个叶子结点为例：如结点A到结点F的路径为：从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的
16、编码。重复和，直到F只含一棵树为止。以第一个叶子结点为例：11的双亲结点为13，且11是13的右孩子，故分支应该标“1”，所以编码“1”入栈。15的双亲结点为0，所以可以判断15就是根结点，那么第一个结点编码完毕，编码应该从栈顶向栈底读，为“0110”。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。这种编码方式也可以对应到二叉树，如右图所式下面对哈夫曼树进行编码，每一个结点的左分支上面标0，右分支上面标1。根据权值3，1，2，1 构造哈夫曼树当A、B、C、D按照如下形式进行编码时。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编
17、码。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。13的双亲结点为15，且13是15的左孩子，故分支应该标“0”，所以编码“0”入栈。可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。WPL=w1*L1+w2*L2+w3*L3+w4*L4这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。当权值为7，5，2，4时，构造哈夫曼树。可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。当A、B、C、D按照如下形式进行编码时。下面对哈夫曼树进行编码，每一个结
18、点的左分支上面标0，右分支上面标1。3211BDCA247 下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA2470 下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA24701 下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA247010 下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA2470101 下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA24701010 下面对哈夫曼树进行编码，每一个结点的左分支上面标1
19、，右分支上面标0。3211BDCA24710101011的双亲结点为13，且11是13的右孩子，故分支应该标“1”，所以编码“1”入栈。9的双亲结点为11，且9是11的右孩子，故分支应该标“1”，所以编码“1”入栈。最优二叉树（哈夫曼树）：给定n个权值w1,w2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。从上面的分析可以看出，一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。对于字符串“ABACCDA”，共有7个字符，4种字符。可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。这样,这些编码恢复成二叉树的形式时,不会形
20、成A,B,C,D恰好为二叉树的叶子结点,如右图当权值为7，5，2，4时，构造哈夫曼树。对于字符串“ABACCDA”，共有7个字符，4种字符。这种编码方式也可以对应到二叉树，如右图所式当权值为7，5，2，4时，构造哈夫曼树。采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。以第一个叶子结点为例：从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。（1）如何构造一棵哈夫曼树。对于字符串“ABACCDA”，共有7个字符，4种字符。对于字符串“ABACCDA”，
21、共有7个字符，4种字符。对于字符串“ABACCDA”，共有7个字符，4种字符。根据权值3，1，2，1 构造哈夫曼树这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图其中A、B、C、D出现的次数分别为3、1、2、1。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA247101010A：0 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA2471
22、01010A：0B：1 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：113211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：1103211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：13211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：103211BDCA247101010 从根结点到各个叶子结点，所经
23、分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：10D：13211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：10D：113211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：1B：110C：10D：1113211BDCA247101010思考 N个权值构造的哈夫曼树，树中结点总数是多少？哈夫曼树中，权值越大的结点越靠近根结点。该论断是否正确？2.哈夫曼编码的具体实现 输入字符及其权重 根据权重构造哈夫曼树 根据哈夫
24、曼树编码下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。路径长度：路径上面的分支个数。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。我们首先通过一个例子来演示一下构造过程。如结
25、点A到结点F的路径为：以第一个叶子结点为例：Len(A-B)+Len(A-C)+Len(A-D)+Len(A-E)+Len(A-F)+Len(A-G)根据权值3，1，2，1 构造哈夫曼树最优二叉树（哈夫曼树）：给定n个权值w1,w2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。对于字符串“ABACCDA”，共有7个字符，4种字符。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。当A、B、C、D按照如下形式进行编码时。以第一个叶子结点为例：如当A、B、C、D按照如下形式进行编码时。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结
26、点所代表字符的编码。以第一个叶子结点为例：15的双亲结点为0，所以可以判断15就是根结点，那么第一个结点编码完毕，编码应该从栈顶向栈底读，为“0110”。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。算法6.12的动态演示（1）存储结构的选择权值分别如下：ABCDEFGH529781423311这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。采用双亲孩子表示法来存储哈夫曼树。（2）初始化weightparentlchildrchild150002290003700048000514000623000730008110009-00010-00011-
27、00012-00013-00014-00015-000(3)建树过程weightparentlchildrchild150002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000第一步第一步weightparentlchildrchild159002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild159002290003700048
28、000514000623000739008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild159002290003700048000514000623000739008110009800010-00011-00012-00013-00014-00015-000weightparentlchildrchild159002290003700048000514000623000739008110009801010-00011-00012-00013-00014-00015-00015的双亲结点为0，所以可以判
29、断15就是根结点，那么第一个结点编码完毕，编码应该从栈顶向栈底读，为“0110”。以第一个叶子结点为例：对于字符串“ABACCDA”，共有7个字符，4种字符。下面对哈夫曼树进行编码，每一个结点的左分支上面标0，右分支上面标1。当权值为7，5，2，4时，构造哈夫曼树。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。以第一个叶子结点为例：其中A、B、C、D出现的次数分别为3、1、2、1。对于字符串“ABACCDA”，共有7个字符，
30、4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。以第一个叶子结点为例：这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图对于字符串“ABACCDA”，共有7个字符，4种字符。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。如结点E的带权路径长度为:Len(E-A)*3=2*3=6以第一个叶子结点为例：以第一个叶子结点为例：从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。其中A、B、C、D出现的次数分别为3、1、2、1。以第一个叶子结点为例：weightparentlchildrchild15
31、9002290003700048000514000623000739008110009801710-00011-00012-00013-00014-00015-000weightparentlchildrchild159002290003700048000514000623000739008110009801710-00011-00012-00013-00014-00015-000第第 二二 步步weightparentlchildrchild1590022900037100048000514000623000739008110009801710-00011-00012-00013-00014
32、-00015-000weightparentlchildrchild15900229000371000481000514000623000739008110009801710-00011-00012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081100098017101500011-00012-00013-00014-00015-000weightparentlchildrchild1590022900037100048100051400062300073900811
33、00098017101503011-00012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081100098017101503411-00012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081100098017101503411-00012-00013-00014-00015-000第第 三三 步步weightparentlchildrchil
34、d1590022900037100048100051400062300073900811110098017101503411-00012-00013-00014-00015-000weightparentlchildrchild15900229000371000481000514000623000739008111100981117101503411-00012-00013-00014-00015-000其中A、B、C、D出现的次数分别为3、1、2、1。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰
35、好为二叉树的叶子结点,如右图那么如何选择L1、L2、L3、L4的值，使得WPL最小呢？如结点A到结点F的路径为：从叶子结点开始，向根回溯，来对叶子结点所代表的字符进行编码。我们首先通过一个例子来演示一下构造过程。之所以会出现二义性，是因为出现了A的编码是C的编码的前缀；其中A、B、C、D出现的次数分别为3、1、2、1。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树对于字符串“ABACCDA”，共有7个
36、字符，4种字符。这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。以第一个叶子结点为例：当权值为7，5，2，4时，构造哈夫曼树。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。当权值为7，5，2，4时，构造哈夫曼树。从上面的分析可以看出，一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。对于字符串“ABACCDA”，共有7个字符，4种字符。weightparentlchildrchild1590022900037100048100051400062
37、30007390081111009811171015034111900012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908912-00013-00014-00015-000weightpare
38、ntlchildrchild159002290003710004810005140006230007390081111009811171015034111908912-00013-00014-00015-000第第 四四 步步weightparentlchildrchild1590022900037100048100051412006230007390081111009811171015034111908912-00013-00014-00015-000weightparentlchildrchild15900229000371000481000514120062300073900811110
39、098111710151234111908912-00013-00014-00015-000weightparentlchildrchild159002290003710004810005141200623000739008111100981117101512341119089122900013-00014-00015-000weightparentlchildrchild159002290003710004810005141200623000739008111100981117101512341119089122905013-00014-00015-000weightparentlchild
40、rchild1590022900037100048100051412006230007390081111009811171015123411190891229051013-00014-00015-000weightparentlchildrchild1590022900037100048100051412006230007390081111009811171015123411190891229051013-00014-00015-000第第 五五 步步weightparentlchildrchild159002290003710004810005141200623130073900811110
41、09811171015123411190891229051013-00014-00015-000weightparentlchildrchild159002290003710004810005141200623130073900811110098111710151234111913891229051013-00014-00015-000对于字符串“ABACCDA”，共有7个字符，4种字符。对于字符串“ABACCDA”，共有7个字符，4种字符。这种编码方式也可以对应到二叉树，如右图所式其中A、B、C、D出现的次数分别为3、1、2、1。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结
42、点所代表字符的编码。根据权值3，1，2，1 构造哈夫曼树当权值为7，5，2，4时，构造哈夫曼树。请将“0111”翻译成字符串。如结点E的带权路径长度为:Len(E-A)*3=2*3=6采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。其中A、B、C、D出现的次数分别为3、1、2、1。对于字符串“ABACCDA”，共有7个字符，4种字符。对于字符串“ABACCDA”，共有7个字符，4种字符。下面对哈夫曼树进行
43、编码，每一个结点的左分支上面标1，右分支上面标0。其中A、B、C、D出现的次数分别为3、1、2、1。对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。WPL=w1*L1+w2*L2+wn*Ln这种编码方式也可以对应到二叉树，如右图所式重复和，直到F只含一棵树为止。weightparentlchildrchild1590022900037100048100051412006231300739008111100981117101512341119138912290510134200014-00015-000weightparentlchildr
44、child1590022900037100048100051412006231300739008111100981117101512341119138912290510134206014-00015-000weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000weightparentlchildrchild15900229000371000481000514120062313007390081111009
45、811171015123411191389122905101342061114-00015-000第第 六六 步步weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342061114-000
46、15-000weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013420611145800015-000weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013420611145802015-000weightparentlchildrchild159002291400371000
47、481000514120062313007390081111009811171015123411191389122914510134206111458021215-000weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134206111458021215-000第第 七七 步步weightparentlchildrchild15900229140037100048100051412006231300739008111100981117
48、10151234111913891229145101342156111458021215-000weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013421561114581521215-000weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134215611145815212
49、15100000weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134215611145815212151000130weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152121510001314（4）编码过程 从叶子结点开始，向根回溯，来对叶子结点
50、所代表的字符进行编码。weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152121510001314以第一个叶子结点为例：1的双亲结点为9，且1是9的左孩子，故分支应该标“0”，所以编码“0”入栈。以第一个叶子结点为例：0以第一个叶子结点为例：9的双亲结点为11，且9是11的右孩子，故分支应该标“1”，所以编码“1”入栈。0以第一个叶子结点为例：01以第一个叶子结点为例：11的双亲结点为13，且11是13的右
