树和二叉树哈夫曼树及其应用课件

树和二叉树哈夫曼树及其应用树和二叉树哈夫曼树及其应用11.相关概念路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。如结点A到结点F的路径为：A-B-E-FABCDEFG1.相关概念ABCDEFG2路径长度：路径上面的分支个数。如A-F的路径长度为3。ABCDEFGABCDEFG3路径长度：路径上面的分支个数。结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。对于字符串“ABACCDA”，共有7个字符，4种字符。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。树的路径长度：从树根到每一个结点的路径长度之和。这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。以第一个叶子结点为例：15的双亲结点为0，所以可以判断15就是根结点，那么第一个结点编码完毕，编码应该从栈顶向栈底读，为“0110”。（1）定长编码---根据出现的字符种数进行编码从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。=1+1+2+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路径长度：路径上面的分支个数。树的路径长度：从树根到每一个结4结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。如左图。ABCDEFG412537结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来5结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘积。如结点E的带权路径长度为:Len(E-A)*3=2*3=6ABCDEFG412537结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘6树的带权路径长度： 树中所有叶子结点的带权路径长度之和。记作：WPL=w1*L1+w2*L2+……+wn*LnABCDEFGw1w2w3w4树的带权路径长度：ABCDEFGw1w2w3w47最优二叉树（哈夫曼树）：给定n个权值{w1,w2,…,wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。构造出来的二叉树的形态可以有多个，我们把其中带权路径长度WPL最小的二叉树称作最优二叉树或者哈夫曼树。ABCDEFGw1w2w3w4最优二叉树（哈夫曼树）：给定n个权值{w1,w2,…,wn}82.哈夫曼算法（1）如何构造一棵哈夫曼树。我们首先通过一个例子来演示一下构造过程。2.哈夫曼算法（1）如何构造一棵哈夫曼树。9当权值为{7，5，2，4}时，构造哈夫曼树。7524当权值为{7，5，2，4}时，构造哈夫曼树。752410当权值为{7，5，2，4}时，构造哈夫曼树。75246当权值为{7，5，2，4}时，构造哈夫曼树。7524611当权值为{7，5，2，4}时，构造哈夫曼树。72465当权值为{7，5，2，4}时，构造哈夫曼树。7246512当权值为{7，5，2，4}时，构造哈夫曼树。7246511当权值为{7，5，2，4}时，构造哈夫曼树。724651113当权值为{7，5，2，4}时，构造哈夫曼树。7246511当权值为{7，5，2，4}时，构造哈夫曼树。724651114当权值为{7，5，2，4}时，构造哈夫曼树。724651118当权值为{7，5，2，4}时，构造哈夫曼树。7246511115（2）哈夫曼算法的语言描述根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复②和③，直到F只含一棵树为止。这棵树便是哈夫曼树。（2）哈夫曼算法的语言描述根据给定的n个权值{w1,w2,…16对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。 现在要对字符串进行0、1编码，有哪些方法？哪一种编码的长度最短？对于字符串“ABACCDA”，共有7个字171.各种编码方式（1）定长编码---根据出现的字符种数进行编码 字符串“ABACCDA”中共出现4种字符，那么可以用2位表示。ABCD000110111.各种编码方式（1）定长编码---根据出现的字符种数进行编18（2）哈夫曼算法的语言描述假设编码过程中有以下对应关系：假设编码过程中有以下对应关系：假设编码过程中有以下对应关系：以第一个叶子结点为例：从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。（2）哈夫曼算法的语言描述=1+1+2+2+3+3=12其中A、B、C、D出现的次数分别为3、1、2、1。N个权值构造的哈夫曼树，树中结点总数是多少？11的双亲结点为13，且11是13的右孩子，故分支应该标“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,…,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）定长编码---根据出现的字符种数进行编码 这种编码方式可以对应到二叉树，如右图所式ABCD00011011ABCD000111（2）哈夫曼算法的语言描述从根结点到各个叶子结点，所经分支上191.各种编码方式（2）变长编码 当A、B、C、D按照如下形式进行编码时。ABCD011010111采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。否则就会出现二义性。1.各种编码方式（2）变长编码ABCD011010111201.各种编码方式（2）变长编码这种编码方式也可以对应到二叉树，如右图所式 ABCD011010111ABC0011D011.各种编码方式（2）变长编码ABCD011010111AB211.各种编码方式（2）变长编码 如当A、B、C、D按照如下形式进行编码时。ABCD01101111请将“0111”翻译成字符串。试一试，有哪些翻译方式。之所以会出现二义性，是因为出现了A的编码是C的编码的前缀；B的编码是D的编码的前缀.1.各种编码方式（2）变长编码ABCD01101111221.各种编码方式（2）变长编码这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图

ABCD01101111ACB0111D11.各种编码方式（2）变长编码ABCD01101111ACB231.各种编码方式从上面的分析可以看出，一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。也可以看出，每一个可用的编码都可以转化成二叉树的形式，这样编码理论便可以与二叉树的一些性质结合起来，就可以应用二叉树的理论知识来解决编码问题。1.各种编码方式从上面的分析可以看出，一个可用的编码必须满足241.各种编码方式（3）哈夫曼编码 假设编码过程中有以下对应关系：字符ABCD权重（字符出现次数）w1w2w3w4编码长度L1L2L3L4那么总的编码长度为：WPL=w1*L1+w2*L2+w3*L3+w4*L4那么如何选择L1、L2、L3、L4的值，使得WPL最小呢？1.各种编码方式（3）哈夫曼编码字符ABCD权重（字符出现次251.各种编码方式（3）哈夫曼编码 可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。1.各种编码方式（3）哈夫曼编码 可以看出，该公式与哈26对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树1231ABCD对于字符串“ABACCDA”，共有7个字符，4种字符。其中27对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA对于字符串“ABACCDA”，共有7个字符，4种字符。其中28对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA2对于字符串“ABACCDA”，共有7个字符，4种字符。其中29对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA2对于字符串“ABACCDA”，共有7个字符，4种字符。其中30对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA24对于字符串“ABACCDA”，共有7个字符，4种字符。其中31对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA24对于字符串“ABACCDA”，共有7个字符，4种字符。其中32对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA247对于字符串“ABACCDA”，共有7个字符，4种字符。其中33下面对哈夫曼树进行编码，每一个结点的左分支上面标0，右分支上面标1。3211BDCA247下面对哈夫曼树进行编码，每一个结点的左分支上面标0，右34下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA2470下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右35下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA24701下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右36下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA247010下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右37下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA2470101下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右38下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA24701010下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右39下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA247101010下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右40从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序41从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA247101010A：0从根结点到各个叶子结点，所经分支上面的0、1序42从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA247101010A：0B：1从根结点到各个叶子结点，所经分支上面的0、1序43从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：113211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序44从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：1103211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序45从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：13211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序46从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：103211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序47从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：10D：13211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序48从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：10D：113211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序49从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：1B：110C：10D：1113211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序50思考N个权值构造的哈夫曼树，树中结点总数是多少？哈夫曼树中，权值越大的结点越靠近根结点。该论断是否正确？思考N个权值构造的哈夫曼树，树中结点总数是多少？512.哈夫曼编码的具体实现输入字符及其权重根据权重构造哈夫曼树根据哈夫曼树编码2.哈夫曼编码的具体实现输入字符及其权重52算法6.12的动态演示（1）存储结构的选择权值分别如下：ABCDEFGH529781423311这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。采用双亲孩子表示法来存储哈夫曼树。算法6.12的动态演示（1）存储结构的选择ABCDEFGH553（2）初始化（2）初始化54weightparentlchildrchild150002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild15000255(3)建树过程(3)建树过程56weightparentlchildrchild150002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000第一步weightparentlchildrchild15000257weightparentlchildrchild159002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild15900258weightparentlchildrchild159002290003700048000514000623000739008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild15900259weightparentlchildrchild159002290003700048000514000623000739008110009800010-00011-00012-00013-00014-00015-000weightparentlchildrchild15900260weightparentlchildrchild159002290003700048000514000623000739008110009801010-00011-00012-00013-00014-00015-000weightparentlchildrchild15900261weightparentlchildrchild159002290003700048000514000623000739008110009801710-00011-00012-00013-00014-00015-000weightparentlchildrchild15900262weightparentlchildrchild159002290003700048000514000623000739008110009801710-00011-00012-00013-00014-00015-000第二步weightparentlchildrchild15900263weightparentlchildrchild1590022900037100048000514000623000739008110009801710-00011-00012-00013-00014-00015-000weightparentlchildrchild15900264weightparentlchildrchild15900229000371000481000514000623000739008110009801710-00011-00012-00013-00014-00015-000weightparentlchildrchild15900265weightparentlchildrchild159002290003710004810005140006230007390081100098017101500011-00012-00013-00014-00015-000weightparentlchildrchild15900266weightparentlchildrchild159002290003710004810005140006230007390081100098017101503011-00012-00013-00014-00015-000weightparentlchildrchild15900267weightparentlchildrchild159002290003710004810005140006230007390081100098017101503411-00012-00013-00014-00015-000weightparentlchildrchild15900268weightparentlchildrchild159002290003710004810005140006230007390081100098017101503411-00012-00013-00014-00015-000第三步weightparentlchildrchild15900269weightparentlchildrchild1590022900037100048100051400062300073900811110098017101503411-00012-00013-00014-00015-000weightparentlchildrchild15900270weightparentlchildrchild15900229000371000481000514000623000739008111100981117101503411-00012-00013-00014-00015-000weightparentlchildrchild15900271weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111900012-00013-00014-00015-000weightparentlchildrchild15900272weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908012-00013-00014-00015-000weightparentlchildrchild15900273weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908912-00013-00014-00015-000weightparentlchildrchild15900274weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908912-00013-00014-00015-000第四步weightparentlchildrchild15900275weightparentlchildrchild1590022900037100048100051412006230007390081111009811171015034111908912-00013-00014-00015-000weightparentlchildrchild15900276weightparentlchildrchild15900229000371000481000514120062300073900811110098111710151234111908912-00013-00014-00015-000weightparentlchildrchild15900277weightparentlchildrchild159002290003710004810005141200623000739008111100981117101512341119089122900013-00014-00015-000weightparentlchildrchild15900278weightparentlchildrchild159002290003710004810005141200623000739008111100981117101512341119089122905013-00014-00015-000weightparentlchildrchild15900279weightparentlchildrchild1590022900037100048100051412006230007390081111009811171015123411190891229051013-00014-00015-000weightparentlchildrchild15900280weightparentlchildrchild1590022900037100048100051412006230007390081111009811171015123411190891229051013-00014-00015-000第五步weightparentlchildrchild15900281weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411190891229051013-00014-00015-000weightparentlchildrchild15900282weightparentlchildrchild159002290003710004810005141200623130073900811110098111710151234111913891229051013-00014-00015-000weightparentlchildrchild15900283weightparentlchildrchild1590022900037100048100051412006231300739008111100981117101512341119138912290510134200014-00015-000weightparentlchildrchild15900284weightparentlchildrchild1590022900037100048100051412006231300739008111100981117101512341119138912290510134206014-00015-000weightparentlchildrchild15900285weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000weightparentlchildrchild15900286weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000第六步weightparentlchildrchild15900287weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000weightparentlchildrchild15900288weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342061114-00015-000weightparentlchildrchild15900289weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013420611145800015-000weightparentlchildrchild15900290weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013420611145802015-000weightparentlchildrchild15900291weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134206111458021215-000weightparentlchildrchild15900292weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134206111458021215-000第七步weightparentlchildrchild15900293weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458021215-000weightparentlchildrchild15900294weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013421561114581521215-000weightparentlchildrchild15900295weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013421561114581521215100000weightparentlchildrchild15900296weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134215611145815212151000130weightparentlchildrchild15900297weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152121510001314weightparentlchildrchild15900298（4）编码过程从叶子结点开始，向根回溯，来对叶子结点所代表的字符进行编码。（4）编码过程从叶子结点开始，向根回溯，来对叶子99weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342156111458152121510001314weightparentlchildrchild159002100以第一个叶子结点为例：1的双亲结点为9，且1是9的左孩子，故分支应该标“0”，所以编码“0”入栈。以第一个叶子结点为例：1的双亲结点为9，且1是9的左孩101以第一个叶子结点为例：0以第一个叶子结点为例：0102以第一个叶子结点为例：9的双亲结点为11，且9是11的右孩子，故分支应该标“1”，所以编码“1”入栈。0以第一个叶子结点为例：9的双亲结点为11，且9是11的103以第一个叶子结点为例：01以第一个叶子结点为例：01104在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。根据权值{3，1，2，1}构造哈夫曼树当权值为{7，5，2，4}时，构造哈夫曼树。其中A、B、C、D出现的次数分别为3、1、2、1。11的双亲结点为13，且11是13的右孩子，故分支应该标“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在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二105以第一个叶子结点为例：011以第一个叶子结点为例：011106以第一个叶子结点为例：13的双亲结点为15，且13是15的左孩子，故分支应该标“0”，所以编码“0”入栈。011以第一个叶子结点为例：13的双亲结点为15，且13是1107以第一个叶子结点为例：0110以第一个叶子结点为例：0110108以第一个叶子结点为例：15的双亲结点为0，所以可以判断15就是根结点，那么第一个结点编码完毕，编码应该从栈顶向栈底读，为“0110”。0110以第一个叶子结点为例：15的双亲结点为0，所以可以判断109同理可以写出其他叶子结点的编码。同理可以写出其他叶子结点的编码。110树和二叉树哈夫曼树及其应用树和二叉树哈夫曼树及其应用1111.相关概念路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。如结点A到结点F的路径为：A-B-E-FABCDEFG1.相关概念ABCDEFG112路径长度：路径上面的分支个数。如A-F的路径长度为3。ABCDEFGABCDEFG113路径长度：路径上面的分支个数。结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。对于字符串“ABACCDA”，共有7个字符，4种字符。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。树的路径长度：从树根到每一个结点的路径长度之和。这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。以第一个叶子结点为例：15的双亲结点为0，所以可以判断15就是根结点，那么第一个结点编码完毕，编码应该从栈顶向栈底读，为“0110”。（1）定长编码---根据出现的字符种数进行编码从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。=1+1+2+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路径长度：路径上面的分支个数。树的路径长度：从树根到每一个结114结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。如左图。ABCDEFG412537结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来115结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘积。如结点E的带权路径长度为:Len(E-A)*3=2*3=6ABCDEFG412537结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘116树的带权路径长度： 树中所有叶子结点的带权路径长度之和。记作：WPL=w1*L1+w2*L2+……+wn*LnABCDEFGw1w2w3w4树的带权路径长度：ABCDEFGw1w2w3w4117最优二叉树（哈夫曼树）：给定n个权值{w1,w2,…,wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。构造出来的二叉树的形态可以有多个，我们把其中带权路径长度WPL最小的二叉树称作最优二叉树或者哈夫曼树。ABCDEFGw1w2w3w4最优二叉树（哈夫曼树）：给定n个权值{w1,w2,…,wn}1182.哈夫曼算法（1）如何构造一棵哈夫曼树。我们首先通过一个例子来演示一下构造过程。2.哈夫曼算法（1）如何构造一棵哈夫曼树。119当权值为{7，5，2，4}时，构造哈夫曼树。7524当权值为{7，5，2，4}时，构造哈夫曼树。7524120当权值为{7，5，2，4}时，构造哈夫曼树。75246当权值为{7，5，2，4}时，构造哈夫曼树。75246121当权值为{7，5，2，4}时，构造哈夫曼树。72465当权值为{7，5，2，4}时，构造哈夫曼树。72465122当权值为{7，5，2，4}时，构造哈夫曼树。7246511当权值为{7，5，2，4}时，构造哈夫曼树。7246511123当权值为{7，5，2，4}时，构造哈夫曼树。7246511当权值为{7，5，2，4}时，构造哈夫曼树。7246511124当权值为{7，5，2，4}时，构造哈夫曼树。724651118当权值为{7，5，2，4}时，构造哈夫曼树。72465111125（2）哈夫曼算法的语言描述根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复②和③，直到F只含一棵树为止。这棵树便是哈夫曼树。（2）哈夫曼算法的语言描述根据给定的n个权值{w1,w2,…126对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。 现在要对字符串进行0、1编码，有哪些方法？哪一种编码的长度最短？对于字符串“ABACCDA”，共有7个字1271.各种编码方式（1）定长编码---根据出现的字符种数进行编码 字符串“ABACCDA”中共出现4种字符，那么可以用2位表示。ABCD000110111.各种编码方式（1）定长编码---根据出现的字符种数进行编128（2）哈夫曼算法的语言描述假设编码过程中有以下对应关系：假设编码过程中有以下对应关系：假设编码过程中有以下对应关系：以第一个叶子结点为例：从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。（2）哈夫曼算法的语言描述=1+1+2+2+3+3=12其中A、B、C、D出现的次数分别为3、1、2、1。N个权值构造的哈夫曼树，树中结点总数是多少？11的双亲结点为13，且11是13的右孩子，故分支应该标“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,…,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）定长编码---根据出现的字符种数进行编码 这种编码方式可以对应到二叉树，如右图所式ABCD00011011ABCD000111（2）哈夫曼算法的语言描述从根结点到各个叶子结点，所经分支上1291.各种编码方式（2）变长编码 当A、B、C、D按照如下形式进行编码时。ABCD011010111采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。否则就会出现二义性。1.各种编码方式（2）变长编码ABCD0110101111301.各种编码方式（2）变长编码这种编码方式也可以对应到二叉树，如右图所式 ABCD011010111ABC0011D011.各种编码方式（2）变长编码ABCD011010111AB1311.各种编码方式（2）变长编码 如当A、B、C、D按照如下形式进行编码时。ABCD01101111请将“0111”翻译成字符串。试一试，有哪些翻译方式。之所以会出现二义性，是因为出现了A的编码是C的编码的前缀；B的编码是D的编码的前缀.1.各种编码方式（2）变长编码ABCD011011111321.各种编码方式（2）变长编码这样,这些编码恢复成二叉树的形式时,不会形成A,B,C,D恰好为二叉树的叶子结点,如右图

ABCD01101111ACB0111D11.各种编码方式（2）变长编码ABCD01101111ACB1331.各种编码方式从上面的分析可以看出，一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。也可以看出，每一个可用的编码都可以转化成二叉树的形式，这样编码理论便可以与二叉树的一些性质结合起来，就可以应用二叉树的理论知识来解决编码问题。1.各种编码方式从上面的分析可以看出，一个可用的编码必须满足1341.各种编码方式（3）哈夫曼编码 假设编码过程中有以下对应关系：字符ABCD权重（字符出现次数）w1w2w3w4编码长度L1L2L3L4那么总的编码长度为：WPL=w1*L1+w2*L2+w3*L3+w4*L4那么如何选择L1、L2、L3、L4的值，使得WPL最小呢？1.各种编码方式（3）哈夫曼编码字符ABCD权重（字符出现次1351.各种编码方式（3）哈夫曼编码 可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。1.各种编码方式（3）哈夫曼编码 可以看出，该公式与哈136对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树1231ABCD对于字符串“ABACCDA”，共有7个字符，4种字符。其中137对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA对于字符串“ABACCDA”，共有7个字符，4种字符。其中138对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA2对于字符串“ABACCDA”，共有7个字符，4种字符。其中139对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA2对于字符串“ABACCDA”，共有7个字符，4种字符。其中140对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA24对于字符串“ABACCDA”，共有7个字符，4种字符。其中141对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA24对于字符串“ABACCDA”，共有7个字符，4种字符。其中142对于字符串“ABACCDA”，共有7个字符，4种字符。其中A、B、C、D出现的次数分别为3、1、2、1。根据权值{3，1，2，1}构造哈夫曼树3211BDCA247对于字符串“ABACCDA”，共有7个字符，4种字符。其中143下面对哈夫曼树进行编码，每一个结点的左分支上面标0，右分支上面标1。3211BDCA247下面对哈夫曼树进行编码，每一个结点的左分支上面标0，右144下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA2470下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右145下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA24701下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右146下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA247010下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右147下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA2470101下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右148下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA24701010下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右149下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右分支上面标0。3211BDCA247101010下面对哈夫曼树进行编码，每一个结点的左分支上面标1，右150从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序151从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA247101010A：0从根结点到各个叶子结点，所经分支上面的0、1序152从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。3211BDCA247101010A：0B：1从根结点到各个叶子结点，所经分支上面的0、1序153从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：113211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序154从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：1103211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序155从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：13211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序156从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：103211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序157从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：10D：13211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序158从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：0B：110C：10D：113211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序159从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。A：1B：110C：10D：1113211BDCA247101010从根结点到各个叶子结点，所经分支上面的0、1序160思考N个权值构造的哈夫曼树，树中结点总数是多少？哈夫曼树中，权值越大的结点越靠近根结点。该论断是否正确？思考N个权值构造的哈夫曼树，树中结点总数是多少？1612.哈夫曼编码的具体实现输入字符及其权重根据权重构造哈夫曼树根据哈夫曼树编码2.哈夫曼编码的具体实现输入字符及其权重162算法6.12的动态演示（1）存储结构的选择权值分别如下：ABCDEFGH529781423311这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。采用双亲孩子表示法来存储哈夫曼树。算法6.12的动态演示（1）存储结构的选择ABCDEFGH5163（2）初始化（2）初始化164weightparentlchildrchild150002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000weightparentlchildrchild150002165(3)建树过程(3)建树过程166weightparentlchildrchild150002290003700048000514000623000730