第5章树和二叉树4.ppt

《第5章树和二叉树4.ppt》由会员分享，可在线阅读，更多相关《第5章树和二叉树4.ppt（39页珍藏版）》请在第壹文秘上搜索。

1、5.1 5.1 树的概念和基本操作树的概念和基本操作5.2 5.2 二叉树二叉树 5.3 5.3 树和森林树和森林5.4 5.4 哈夫曼树及其应用哈夫曼树及其应用5.5 5.5 应用举例应用举例v5.4.1 哈夫曼树的基本概念哈夫曼树的基本概念v5.4.2 哈夫曼树的构造算法哈夫曼树的构造算法v5.4.3 哈夫曼编码哈夫曼编码v5.4.4 哈夫曼编码的算法实现哈夫曼编码的算法实现1.1.路径路径:从树中一个结点到另一个结从树中一个结点到另一个结点之间的分支构成两个结点之间的点之间的分支构成两个结点之间的路径路径.2.2.路径长度路径长度:是指从根结点到该结点的是指从根结点到该结点的路径上分支的

2、数目。路径上分支的数目。3.3.树的路径长度树的路径长度:从树根到每个结点的从树根到每个结点的路径长度之和。完全二叉树就是这路径长度之和。完全二叉树就是这种路径长度最短的二叉树种路径长度最短的二叉树.4.4.结点的结点的带权带权路径长度路径长度：是从该结点到：是从该结点到树根之间的路径长度与结点上权值的树根之间的路径长度与结点上权值的乘积乘积.5.5.树的带权树的带权路径长度路径长度：树中所有：树中所有叶子叶子结结点的带权路径长度之和点的带权路径长度之和.通常记作通常记作:n nWPL=wWPL=wk kl lk k k=1k=1其中：其中：WWk k：第：第k k个叶子结点的权值；个叶子结点

3、的权值；L Lk k：第：第k k个叶子结点的路径长度个叶子结点的路径长度.v6.6.哈夫曼树（最优二叉树）哈夫曼树（最优二叉树）是指对于一组带有确定权值的叶子结点构是指对于一组带有确定权值的叶子结点构造的具有最小带权路径长度的二叉树。造的具有最小带权路径长度的二叉树。即：即：设有给定的设有给定的 n n 个权值个权值 w w1 1,w,w2 2,w,wn n，构造一棵由构造一棵由 n n个叶子结点的个叶子结点的,每个叶子结点每个叶子结点的带权为的带权为 w wi i,则其中带权路径长度则其中带权路径长度 WPLWPL最最小的小的二叉树称为最优树或哈夫曼树二叉树称为最优树或哈夫曼树.27549

4、WPL=72+52+23+43+92 =60WPL=74+94+53+42+21 =89 7 9 254 根据给定的根据给定的 n n 个权值个权值 w w1 1,w,w2 2,w,wn n，构造构造 n n 棵二叉树的集合棵二叉树的集合 F F=T=T1 1,T,T2 2,T,Tn n，其中每棵二叉树中均只含一个带权值其中每棵二叉树中均只含一个带权值 为为 w wi i 的根结点的根结点,其左、右子树为空树其左、右子树为空树;(1)(哈夫曼算法)以二叉树为例:在在 F 中选取其根结点的权值中选取其根结点的权值为最小的两棵二叉树，分别作为为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树

5、，左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值值为其左、右子树根结点的权值之和之和;(2)从F中删去这两棵树，同时加入 刚生成的新树;重复(2)和(3)两步，直至 F 中只 含一棵树为止。(3)(4)例如:已知权值 W=8,6,2,4 构造哈夫曼树的过程4862246868612246第一步第一步:第二步第二步:第三步第三步:图图5-23 构造哈夫曼树的过程第四步第四步:861224620图图5-23 构造哈夫曼树的过程v由哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结

6、点越靠远离根结点。在构造哈夫曼树时，可设置一个结构数组在构造哈夫曼树时，可设置一个结构数组HuffNodeHuffNode保存各结点的信息，数组保存各结点的信息，数组HuffNodeHuffNode的的大小为：大小为：2n-1,2n-1,数组元素的结构形式：数组元素的结构形式：weight lchild rchild parent结点的权值结点的权值1.1.前缀编码前缀编码在电报传送的过程中在电报传送的过程中,传送的电文以二进制代传送的电文以二进制代码作为电报编码码作为电报编码.例如例如:电文电文:“:“ABAACCBADCA”,ABAACCBADCA”,电文中只含电文中只含四个字符四个字符:

7、A,B,C,D,A,B,C,D,每个字符用两位每个字符用两位定长定长编编码码,例如：例如：A:00;A:00;B:01B:01;C:10C:10;D:11D:11.则上述电文可译为则上述电文可译为:00000101000000001010101001010000111110100000 A B AA CC B A D C AA B AA CC B A D C A总长总长2222位位,接收方按两位一组译码即可接收方按两位一组译码即可.由于采用定长编码的电文总长无法缩短由于采用定长编码的电文总长无法缩短,因此因此,对字符采用对字符采用不定长不定长编码编码.且让电文中且让电文中出现次数较多的字符采用

8、尽可能短的编出现次数较多的字符采用尽可能短的编码码,从而尽可能的减小电文总长从而尽可能的减小电文总长.例如例如:上例中上例中,A,CA,C出现的频率较高出现的频率较高,对对A,A,B B,C,C,D D的编码分别为的编码分别为:0,0,0000,1,1,0101,则电文总则电文总长长:14:14位的二进制串位的二进制串:“:“0000011000011000000110000110”,”,长度长度缩短了但译码出现的困难缩短了但译码出现的困难.前缀编码前缀编码:是指任何一个字符的编码都不是指任何一个字符的编码都不是另一个字符编码的前缀是另一个字符编码的前缀.2.2.哈夫曼编码哈夫曼编码以每种字符

9、在电文中出现的次数为以每种字符在电文中出现的次数为WWi i,其编码长度为其编码长度为l li i,电文中可能出现的电文中可能出现的字符有字符有n n种种,则电文总长为则电文总长为:n nWPL=wili i=1正好是对应的哈夫曼树的正好是对应的哈夫曼树的WPL.WPL.因此因此以哈夫曼树来设计的二进制前缀编以哈夫曼树来设计的二进制前缀编码使得电文总长最短码使得电文总长最短.具体设计如下具体设计如下:将可能出现的字符作为叶子结点将可能出现的字符作为叶子结点,电文中字电文中字符出现的频率为各个叶子结点的权值符出现的频率为各个叶子结点的权值,设设计一棵哈夫曼树计一棵哈夫曼树,树的树的左分支左分支表

10、示二进制表示二进制数数0 0，右分支右分支表示二进制数表示二进制数1 1,则从根结点则从根结点到每一个叶子结点（字符）的路经上分到每一个叶子结点（字符）的路经上分支字符组成的字符串，即为该字符的二支字符组成的字符串，即为该字符的二进制前缀编码进制前缀编码,又称为又称为哈夫曼编码哈夫曼编码.例如例如:字符字符A,B,C,DA,B,C,D出现的频率为出现的频率为0.4,0.2,0.3,0.10.4,0.2,0.3,0.1则得到如图所示的哈则得到如图所示的哈夫曼夫曼树树及哈及哈夫曼编码。夫曼编码。哈夫曼编码：A：0C：10B：110D：111ACBD010110ABCD0.40.20.30.1(a)

11、字符出现的频率字符出现的频率(b)哈夫曼树哈夫曼树图5-24 哈夫曼编码设计示例哈夫曼编码设计示例9562725769767139257第一步第一步:第二步第二步:第三步第三步:图5-25 构造哈夫曼树并设计编码构造哈夫曼树并设计编码例如例如:已知权值已知权值 W=5,6,2,9,7 W=5,6,2,9,7 构造哈夫曼树构造哈夫曼树并设计哈夫曼编码并设计哈夫曼编码952 71667 13 2900001111000111100101第四步第四步:图5-25 构造哈夫曼树并设计编码构造哈夫曼树并设计编码1.1.一棵哈夫曼树有个一棵哈夫曼树有个m m叶子结点叶子结点,则其结点总数为则其结点总数为_

12、._.2.2.设电文中出现的字母为设电文中出现的字母为A A，B B，C C，D D和和E E，每个，每个字母在电文中出现的次数分别是字母在电文中出现的次数分别是6 6，2323，3 3，5 5，和和1212，按哈夫曼编码，则字母，按哈夫曼编码，则字母C C的编码应是（）的编码应是（）A A10 B.110 C.1110 D.111110 B.110 C.1110 D.11113.3.设给定权集设给定权集W=2W=2，3 3，4 4，7 7，8 8，99，试构造关，试构造关于于w w的一棵哈夫曼树，并求其加权路径长度的一棵哈夫曼树，并求其加权路径长度WPL.WPL.4.4.有一份电文中共使用有

13、一份电文中共使用5 5个字符：个字符：a,b,c,d,e,a,b,c,d,e,他们的他们的出现频率依次为出现频率依次为4 4，7 7，5 5，2 2，9 9，试画出对应，试画出对应的哈夫曼树（请按左子树根结点的权小于等的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。每个字符的哈夫曼编码。5.5.如下图所示如下图所示 ,以数据集以数据集44，5 5，6 6，7 7，1010，1212，1818为结点权值所构成的哈夫曼树为为结点权值所构成的哈夫曼树为_，其，其带权路径长度为带权路径长度为_。1、查询二叉树中某个

14、结点、查询二叉树中某个结点2、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数3、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)4、由前序、由前序+中序序列构造二叉树中序序列构造二叉树5、创建二叉树的二叉链表存储、创建二叉树的二叉链表存储1).1).在二叉树不空的前提下在二叉树不空的前提下,和根结点的元素进行比和根结点的元素进行比较较,若相等若相等,则找到返回则找到返回 该结点该结点;2).2).否则在左子树中进行查找否则在左子树中进行查找,若找到若找到,则返回该结点则返回该结点;3).3).否则继续在右子树中进行查找否则继续在右子树中进行查找,若找到若找到,则返回则返回该结点该结点

15、,否则返回空。否则返回空。1 1、查询二叉树中某个结点、查询二叉树中某个结点分三步进行分三步进行:BiTree search(BiTree*bt,elemtype x)/在bt为根结点的二叉树中查找元素x BiTree p;p=bt;if(p-data=x)return bt;/查找成功返回 if(bt-lchild!=NULL)return(search(p-lchild,x);if(bt-rchild!=NULL)return(search(p-rchild,x);return NULL;/查找失败 2、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想:中序遍

16、历二叉树，在遍历过程中查找叶子结点，中序遍历二叉树，在遍历过程中查找叶子结点，并计数。并计数。因此，需在遍历算法中增添一个因此，需在遍历算法中增添一个“计数计数”的参数，的参数，并将算法中并将算法中“访问结点访问结点”的操作改为的操作改为:若是叶子结若是叶子结点，则计数器增点，则计数器增1 1。分三种情况。分三种情况:1)1)二叉树为空二叉树为空,则叶子结点数为则叶子结点数为0.0.2)2)若只一个根结点若只一个根结点,则叶子结点数为则叶子结点数为1.1.3)3)若二叉树非空若二叉树非空,分别统计左分别统计左,右子树中叶子结点数右子树中叶子结点数.void CountLeaf(BiTree*bt,int count)if(bt!=NULL)if(!bt-lchild)&(!bt-rchild)count+;/对叶子结点计数对叶子结点计数 CountLeaf(bt-lchild,count);CountLeaf(bt-rchild,count);/if/CountLeafint CountLeaf(BiTree T)/返回指针返回指针T所指二叉树中所有叶子结点个数所指二叉树中所有叶子结点