1、树和二叉树哈夫曼树及其应用1.相关概念路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。如结点A到结点F的路径为：A-B-E-FABCDEFG路径长度：路径上面的分支个数。如A-F的路径长度为3。ABCDEFG路径长度：路径上面的分支个数。结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。对于字符串“ABACCDA”，共有7个字符，4种字符。从根结点到各个叶子结点，所经分支上面的
2、0、1序列，就是该叶子结点所代表字符的编码。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。树的路径长度：从树根到每一个结点的路径长度之和。这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。以第一个叶子结点为例：15的双亲结点为0，所以可以判断15就是根结点，那么第一个结点编码完毕，编码应该从栈顶向栈底读，为“0110”。（1）定长编码-根据出现的字符种数进行编码从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。=1+1+2+
3、2+3+3=12树的路径长度：从树根到每一个结点的路径长度之和。如左边树的路径长度为：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结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘积。如结点E的带权路径长度为:Len(E-A)*3=2*3=6ABCDEFG412537树的带权路径长度：树中所有叶子结点的带权路径长度之和。记作：WPL=w1*L1
4、+w2*L2+wn*LnABCDEFGw1w2w3w4最优二叉树（哈夫曼树）：给定n个权值w1,w2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。构造出来的二叉树的形态可以有多个，我们把其中带权路径长度WPL最小的二叉树称作最优二叉树或者哈夫曼树。ABCDEFGw1w2w3w42.哈夫曼算法（1）如何构造一棵哈夫曼树。我们首先通过一个例子来演示一下构造过程。当权值为7，5，2，4时，构造哈夫曼树。7524当权值为7，5，2，4时，构造哈夫曼树。75246当权值为7，5，2，4时，构造哈夫曼树。72465当权值为7，5，2，4时，构造哈夫曼树。7246511当权值为7，5，2
5、，4时，构造哈夫曼树。7246511当权值为7，5，2，4时，构造哈夫曼树。724651118（2）哈夫曼算法的语言描述根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复和，直到F只含一棵树为止。这棵树便是哈夫曼树。对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。现在要对字
6、符串进行0、1编码，有哪些方法？哪一种编码的长度最短？1.各种编码方式（1）定长编码-根据出现的字符种数进行编码字符串“ABACCDA”中共出现4种字符，那么可以用2位表示。ABCD00011011（2）哈夫曼算法的语言描述假设编码过程中有以下对应关系：假设编码过程中有以下对应关系：假设编码过程中有以下对应关系：以第一个叶子结点为例：从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。（2）哈夫曼算法的语言描述=1+1+2+2+3+3=12其中A、B、C、D出现的次数分别为3、1、2、1。N个权值构造的哈夫曼树，树中结点总数是多少？11的双亲结点为13，且11是1
7、3的右孩子，故分支应该标“1”，所以编码“1”入栈。路径长度：路径上面的分支个数。根据权值3，1，2，1 构造哈夫曼树结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。当权值为7，5，2，4时，构造哈夫曼树。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。如A-F的路径长度为3。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。Len(A-B)+Len(A-C)+Len(A-D)+Len(A-E)+Len(A-F)+Len(A-G)路径长度：路径上面的分支个数。根据给定的n个权值w1,w2
8、,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。树和二叉树哈夫曼树及其应用以第一个叶子结点为例：试一试，有哪些翻译方式。11的双亲结点为13，且11是13的右孩子，故分支应该标“1”，所以编码“1”入栈。路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。下面对哈夫曼树进行编码，每一个结点的左分支上面标0，右分支上面标1。其中A、B、C、D出现的次数分别为3、1、2、1。这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。WPL=w1*L1+w2*L2+wn*Ln1.各种编码方式（1）定长编码-根据
9、出现的字符种数进行编码这种编码方式可以对应到二叉树，如右图所式ABCD00011011ABCD0001111.各种编码方式（2）变长编码当A、B、C、D按照如下形式进行编码时。ABCD011010111 采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。否则就会出现二义性。1.各种编码方式（2）变长编码这种编码方式也可以对应到二叉树，如右图所式ABCD011010111ABC0011D011.各种编码方式（2）变长编码如当A、B、C、D按照如下形式进行编码时。ABCD01101111 请将“0111”翻译成字符串。试一试，有哪些翻译方式。之所以会出现二义
10、性，是因为出现了A的编码是C的编码的前缀；B的编码是D的编码的前缀.1.各种编码方式（2）变长编码这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图ABCD01101111ACB0111D11.各种编码方式从上面的分析可以看出，一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。也可以看出，每一个可用的编码都可以转化成二叉树的形式，这样编码理论便可以与二叉树的一些性质结合起来，就可以应用二叉树的理论知识来解决编码问题。1.各种编码方式（3）哈夫曼编码假设编码过程中有以下对应关系：字符ABCD权重（字符出现次数）w1 w2 w3 w4编码长度L1L2L
11、3L4 那么总的编码长度为：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”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树3211BDCA 对于字符串“A
12、BACCDA”，共有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 构造哈夫曼树3211BDCA24 对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造
13、哈夫曼树3211BDCA24 对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值3，1，2，1 构造哈夫曼树3211BDCA247 下面对哈夫曼树进行编码，每一个结点的左分支上面标0，右分支上面标1。3211BDCA247 下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA2470 下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA24701 下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA247010 下面对哈夫曼树进行编码，每
14、一个结点的左分支上面标1，右分支上面标0。3211BDCA2470101 下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA24701010 下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA247101010A：0 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编
15、码。3211BDCA247101010A：0B：1 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：113211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：1103211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：13211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：103211BDCA247101010
16、从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：10D：13211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：10D：113211BDCA247101010 从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：1B：110C：10D：1113211BDCA247101010思考 N个权值构造的哈夫曼树，树中结点总数是多少？哈夫曼树中，权值越大的结点越靠近根结点。该论断是否正确？2.哈夫曼编码的具体实现 输入字符及其权重 根
17、据权重构造哈夫曼树 根据哈夫曼树编码算法6.12的动态演示（1）存储结构的选择权值分别如下：ABCDEFGH529781423311这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。采用双亲孩子表示法来存储哈夫曼树。（2）初始化weightparentlchildrchild150002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000(3)建树过程weightparentlchildrchild15000229000370004800051400062300073
18、0008110009-00010-00011-00012-00013-00014-00015-000第一步第一步weightparentlchildrchild159002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild159002290003700048000514000623000739008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild15
19、9002290003700048000514000623000739008110009800010-00011-00012-00013-00014-00015-000weightparentlchildrchild159002290003700048000514000623000739008110009801010-00011-00012-00013-00014-00015-000weightparentlchildrchild159002290003700048000514000623000739008110009801710-00011-00012-00013-00014-00015-00
20、0weightparentlchildrchild159002290003700048000514000623000739008110009801710-00011-00012-00013-00014-00015-000第第 二二 步步weightparentlchildrchild1590022900037100048000514000623000739008110009801710-00011-00012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081100098
21、01710-00011-00012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081100098017101500011-00012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081100098017101503011-00012-00013-00014-00015-000weightparentlchildrchild1590022900037
22、10004810005140006230007390081100098017101503411-00012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081100098017101503411-00012-00013-00014-00015-000第第 三三 步步weightparentlchildrchild1590022900037100048100051400062300073900811110098017101503411-00012-00013-00014-0
23、0015-000weightparentlchildrchild15900229000371000481000514000623000739008111100981117101503411-00012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111900012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390
24、081111009811171015034111908012-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908912-00013-00014-00015-000weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908912-00013-00014-00015-000第第 四四 步步weightpare
25、ntlchildrchild1590022900037100048100051412006230007390081111009811171015034111908912-00013-00014-00015-000weightparentlchildrchild15900229000371000481000514120062300073900811110098111710151234111908912-00013-00014-00015-000weightparentlchildrchild15900229000371000481000514120062300073900811110098111
26、7101512341119089122900013-00014-00015-000weightparentlchildrchild159002290003710004810005141200623000739008111100981117101512341119089122905013-00014-00015-000weightparentlchildrchild1590022900037100048100051412006230007390081111009811171015123411190891229051013-00014-00015-000weightparentlchildrchi
27、ld1590022900037100048100051412006230007390081111009811171015123411190891229051013-00014-00015-000第第 五五 步步weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411190891229051013-00014-00015-000weightparentlchildrchild159002290003710004810005141200623130073900811110098
28、111710151234111913891229051013-00014-00015-000weightparentlchildrchild1590022900037100048100051412006231300739008111100981117101512341119138912290510134200014-00015-000weightparentlchildrchild1590022900037100048100051412006231300739008111100981117101512341119138912290510134206014-00015-000weightpare
29、ntlchildrchild15900229000371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000第第 六六 步步weightparentlchildrchild15900229140037100048100051412006
30、2313007390081111009811171015123411191389122905101342061114-00015-000weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342061114-00015-000weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013
31、420611145800015-000weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013420611145802015-000weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134206111458021215-000weightparentlchildrchild1590
32、02291400371000481000514120062313007390081111009811171015123411191389122914510134206111458021215-000第第 七七 步步weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458021215-000weightparentlchildrchild15900229140037100048100051412006231300739
33、008111100981117101512341119138912291451013421561114581521215-000weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013421561114581521215100000weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510
34、134215611145815212151000130weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152121510001314（4）编码过程 从叶子结点开始，向根回溯，来对叶子结点所代表的字符进行编码。weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914
35、5101342156111458152121510001314以第一个叶子结点为例：1的双亲结点为9，且1是9的左孩子，故分支应该标“0”，所以编码“0”入栈。以第一个叶子结点为例：0以第一个叶子结点为例：9的双亲结点为11，且9是11的右孩子，故分支应该标“1”，所以编码“1”入栈。0以第一个叶子结点为例：01在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。根据权值3，1，2，1 构造哈夫曼树当权值为7，5，2，4时，构造哈夫曼树。其中A、B、C、D出现的次数分别为3、1、2、1。11的双亲结点为13，且11是13
36、的右孩子，故分支应该标“1”，所以编码“1”入栈。9的双亲结点为11，且9是11的右孩子，故分支应该标“1”，所以编码“1”入栈。如A-F的路径长度为3。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。其中A、B、C、D出现的次数分别为3、1、2、1。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。对于字符串“ABACCDA”，共有7个字符，4种字符。这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。根据权值3，1，2，1 构造哈夫曼树重复和，直到F只含一棵树为止。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。以第一个叶子结点为例：11的双亲结点为13，且11是13的右孩子，故分支应该标“1”，所以编码“1”入栈。01以第一个叶子结点为例：011以第一个叶子结点为例：13的双亲结点为15，且13是15的左孩子，故分支应该标“0”，所以编码“0”入栈。011以第一个叶子结点为例：0110以第一个叶子结点为例：15的双亲结点为0，所以可以判断15就是根结点，那么第一个结点编码完毕，编码应该从栈顶向栈底读，为“0110”。0110同理可以写出其他叶子结点的编码。
