树和二叉树哈夫曼树及其应用PPT学习教案

1、会计学1树和二叉树哈夫曼树及其应用树和二叉树哈夫曼树及其应用ABCDEFG第1页/共111页ABCDEFG第2页/共111页ABCDEFG第3页/共111页ABCDEFG412537第4页/共111页ABCDEFG412537第5页/共111页ABCDEFGw1w2w3w4第6页/共111页ABCDEFGw1w2w3w4第7页/共111页第8页/共111页7524第9页/共111页75246第10页/共111页72465第11页/共111页7246511第12页/共111页7246511第13页/共111页724651118第14页/共111页第15页/共111页第16页/共111页ABCD0

2、0011011那么字符串“ABACCDA”的编码将为“00010010101100”，总长度为7*2=14位第17页/共111页ABCD00011011ABCD000111第18页/共111页ABCD011010111 那么字符串“ABACCDA”的编码将为“0110010101110”，总长度为13位，比第二种方式又要短。 采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。否则就会出现二义性。第19页/共111页ABCD011010111ABC0011D01第20页/共111页ABCD01101111 请将“0111”翻译成字符串。试一试，有哪些翻译方

3、式。之所以会出现二义性，是因为出现了A的编码是C的编码的前缀； B的编码是D的编码的前缀.第21页/共111页ABCD01101111ACB0111D1第22页/共111页第23页/共111页字符ABCD权重（字符出现次数）w1 w2 w3 w4编码长度L1L2L3L4 那么总的编码长度为： WPL=w1*L1+w2*L2+w3*L3+w4*L4 那么如何选择L1、L2、L3、L4的值，使得WPL最小呢？第24页/共111页可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。第25页/共111页1231ABCD第26页/共111页3211BDCA第2

4、7页/共111页3211BDCA2第28页/共111页3211BDCA2第29页/共111页3211BDCA24第30页/共111页3211BDCA24第31页/共111页3211BDCA247第32页/共111页3211BDCA247第33页/共111页3211BDCA2470第34页/共111页3211BDCA24701第35页/共111页3211BDCA247010第36页/共111页3211BDCA2470101第37页/共111页3211BDCA24701010第38页/共111页3211BDCA247101010第39页/共111页3211BDCA247101010第40页/共11

5、1页3211BDCA247101010A：0第41页/共111页3211BDCA247101010A：0B：1第42页/共111页A：0B：113211BDCA247101010第43页/共111页A：0B：1103211BDCA247101010第44页/共111页A：0B：110C：13211BDCA247101010第45页/共111页A：0B：110C：103211BDCA247101010第46页/共111页A：0B：110C：10D：13211BDCA247101010第47页/共111页A：0B：110C：10D：113211BDCA247101010第48页/共111页A：1B

6、：110C：10D：1113211BDCA247101010第49页/共111页第50页/共111页第51页/共111页ABCDEFGH529781423311这八个权值作为叶子结点，最终形成的哈夫曼树应共有2*8-1=15个结点。采用双亲孩子表示法来存储哈夫曼树。第52页/共111页第53页/共111页weightparentlchildrchild150002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000第54页/共111页第55页/共111页weightparentlchild

7、rchild150002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000第一步第一步第56页/共111页weightparentlchildrchild159002290003700048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000第57页/共111页weightparentlchildrchild159002290003700048000514000623000739008110009-0001

8、0-00011-00012-00013-00014-00015-000第58页/共111页weightparentlchildrchild159002290003700048000514000623000739008110009800010-00011-00012-00013-00014-00015-000第59页/共111页weightparentlchildrchild159002290003700048000514000623000739008110009801010-00011-00012-00013-00014-00015-000第60页/共111页weightparentlchil

9、drchild159002290003700048000514000623000739008110009801710-00011-00012-00013-00014-00015-000第61页/共111页weightparentlchildrchild159002290003700048000514000623000739008110009801710-00011-00012-00013-00014-00015-000第第 二二 步步第62页/共111页weightparentlchildrchild15900229000371000480005140006230007390081100098

10、01710-00011-00012-00013-00014-00015-000第63页/共111页weightparentlchildrchild15900229000371000481000514000623000739008110009801710-00011-00012-00013-00014-00015-000第64页/共111页weightparentlchildrchild159002290003710004810005140006230007390081100098017101500011-00012-00013-00014-00015-000第65页/共111页weightpa

11、rentlchildrchild159002290003710004810005140006230007390081100098017101503011-00012-00013-00014-00015-000第66页/共111页weightparentlchildrchild159002290003710004810005140006230007390081100098017101503411-00012-00013-00014-00015-000第67页/共111页weightparentlchildrchild1590022900037100048100051400062300073900

12、81100098017101503411-00012-00013-00014-00015-000第第 三三 步步第68页/共111页weightparentlchildrchild1590022900037100048100051400062300073900811110098017101503411-00012-00013-00014-00015-000第69页/共111页weightparentlchildrchild15900229000371000481000514000623000739008111100981117101503411-00012-00013-00014-00015-

13、000第70页/共111页weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111900012-00013-00014-00015-000第71页/共111页weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908012-00013-00014-00015-000第72页/共111页weightparentlchildrchild1590022900037

14、10004810005140006230007390081111009811171015034111908912-00013-00014-00015-000第73页/共111页weightparentlchildrchild159002290003710004810005140006230007390081111009811171015034111908912-00013-00014-00015-000第第 四四 步步第74页/共111页weightparentlchildrchild1590022900037100048100051412006230007390081111009811171

15、015034111908912-00013-00014-00015-000第75页/共111页weightparentlchildrchild15900229000371000481000514120062300073900811110098111710151234111908912-00013-00014-00015-000第76页/共111页weightparentlchildrchild159002290003710004810005141200623000739008111100981117101512341119089122900013-00014-00015-000第77页/共11

16、1页weightparentlchildrchild159002290003710004810005141200623000739008111100981117101512341119089122905013-00014-00015-000第78页/共111页weightparentlchildrchild1590022900037100048100051412006230007390081111009811171015123411190891229051013-00014-00015-000第79页/共111页weightparentlchildrchild15900229000371000

17、48100051412006230007390081111009811171015123411190891229051013-00014-00015-000第第 五五 步步第80页/共111页weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411190891229051013-00014-00015-000第81页/共111页weightparentlchildrchild15900229000371000481000514120062313007390081111009

18、8111710151234111913891229051013-00014-00015-000第82页/共111页weightparentlchildrchild1590022900037100048100051412006231300739008111100981117101512341119138912290510134200014-00015-000第83页/共111页weightparentlchildrchild159002290003710004810005141200623130073900811110098111710151234111913891229051013420601

19、4-00015-000第84页/共111页weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000第85页/共111页weightparentlchildrchild15900229000371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000第第 六六 步步第86页/共111页weigh

20、tparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122905101342061114-00015-000第87页/共111页weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710151234111913891229145101342061114-00015-000第88页/共111页weightparentlchildrchild159002291400

21、37100048100051412006231300739008111100981117101512341119138912291451013420611145800015-000第89页/共111页weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013420611145802015-000第90页/共111页weightparentlchildrchild1590022914003710004810005141200623130073

22、90081111009811171015123411191389122914510134206111458021215-000第91页/共111页weightparentlchildrchild159002291400371000481000514120062313007390081111009811171015123411191389122914510134206111458021215-000第第 七七 步步第92页/共111页weightparentlchildrchild1590022914003710004810005141200623130073900811110098111710

23、151234111913891229145101342156111458021215-000第93页/共111页weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013421561114581521215-000第94页/共111页weightparentlchildrchild15900229140037100048100051412006231300739008111100981117101512341119138912291451013421561114581521215100000第95页/共111页weightparentlchildrchild15900