第5章树和二叉树4ppt课件

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 哈夫曼编码的算法实现哈夫曼编码的算法实现. .4. 4.结点的带权路径长度：是从该结点到结点的带权路径长度：是从该结点到树根之间的路径长度与结点上权值的树根之间的路径长度与结点上权值的乘积乘积. .5. 5.树的带权路径长度：树中所有叶子结树的带权路径长度：

2、树中所有叶子结点的带权路径长度之和点的带权路径长度之和. .通常记作通常记作: : n nWPL = wklkWPL = wklk k=1 k=1其中：其中：WkWk：第：第k k个叶子结点的权值；个叶子结点的权值； Lk Lk：第：第k k个叶子结点的路径长度个叶子结点的路径长度. .v6.6.哈夫曼树最优二叉树）哈夫曼树最优二叉树）v v是指对于一组带有确定权值的叶子结点是指对于一组带有确定权值的叶子结点构造的具有最小带权路径长度的二叉树。构造的具有最小带权路径长度的二叉树。即：即：v设有给定的设有给定的 n n 个权值个权值 w1, w2, , w1, w2, , wnwn，v构造一棵由

3、构造一棵由 n n个叶子结点的个叶子结点的, , 每个叶子每个叶子结点的带权为结点的带权为 wi, wi,则其中带权路径长度则其中带权路径长度 WPLWPL最小的二叉树称为最优树或哈夫曼树最小的二叉树称为最优树或哈夫曼树. .27549WPL= 72+52+23+43+92 =60WPL= 74+94+53+42+21 =89 7 9 254 根据给定的 n 个权值 w1, w2, , wn， 构造 n 棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点,其左、右子树为空树;(1)(哈夫曼算法) 以二叉树为例: 在 F 中选取其根结点的权值

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

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

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

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

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

9、的权值, ,设计一棵哈夫曼设计一棵哈夫曼树树, ,树的左分支表示二进制数树的左分支表示二进制数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：

10、10B：110D ：111ACBD010110ABCD0.40.20.30.1(a) 字符出现的频率字符出现的频率(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叶子

11、结点叶子结点, ,则其结点总数为则其结点总数为_._.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的一棵哈夫曼树，并求其加权路径长度的一棵哈夫曼树，

12、并求其加权路径长度WPL.WPL.4. 4. 有一份电文中共使用有一份电文中共使用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为结点权值所构成的哈夫曼树为为结点权值所构成的哈

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

14、;3). 3). 否则继续在右子树中进行查找否则继续在右子树中进行查找, ,若找到若找到, ,则返回则返回该结点该结点, ,否则返回空。否则返回空。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-rchil

15、d!=NULL) return (search(p-rchild,x); return NULL; /查找失败查找失败 2、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想: :中序遍历二叉树，在遍历过程中查找叶子结点，中序遍历二叉树，在遍历过程中查找叶子结点，并计数。并计数。因此，需在遍历算法中增添一个因此，需在遍历算法中增添一个“计数的参数，计数的参数，并将算法中并将算法中“访问结点的操作改为访问结点的操作改为: :若是叶子结若是叶子结点，则计数器增点，则计数器增1 1。分三种情况。分三种情况: : 1) 1)二叉树为空二叉树为空, ,则叶子结点数为则叶子结点

16、数为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 (

17、BiTree T)/返回指针T所指二叉树中所有叶子结点个数 if (!T ) return 0; /二叉树为空 if (!T-lchild & !T-rchild) return 1; /二叉树中只一个根结点 else m = CountLeaf( T-lchild); n = CountLeaf( T-rchild); return (m+n); /else / CountLeaf3 3、求二叉树的深度、求二叉树的深度( (后序遍历后序遍历) )算法基本思想算法基本思想: : 从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算

18、法中“访问结点的操作为:求得左、右子树深度的最大值，然后加 1 。 首先分析二叉树的深度和它的左、右子树深度之间的关系。int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; /二叉树为空 else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;例例4、二叉树的确定、二叉树的确定前序后序）前序后序） 中

19、序中序 唯一确定一棵二叉树唯一确定一棵二叉树 例例: 前序前序: A、B、D、E、F、C 中序中序: D、B、E、F、A、C确定过程确定过程: : 1 1、确定根、确定根 A; A;2 2、在中序序列中找到、在中序序列中找到 A; A;3 3、中序序列中的、中序序列中的 A A 的左部为的左部为 A A 的的左子树上的所有结点左子树上的所有结点,A ,A 的右部为的右部为 A A 的右子树中的所有结点的右子树中的所有结点; ;4 4、根据、根据 A A 的左子树的所有结点的的左子树的所有结点的前序序列确定前序序列确定 A A 的左子树的根节点，的左子树的根节点，它是它是 A A 的左儿子的左儿

20、子; ;5 5、根据、根据 A A 的右子树的所有结点的的右子树的所有结点的前序序列确定前序序列确定 A A 的右子树的根节点，的右子树的根节点，它是它是 A A 的右儿子的右儿子; ;6 6、 在左、右子树中反复以上过程。在左、右子树中反复以上过程。至所有结点处理完毕至所有结点处理完毕, ,终了终了. . 前序前序: A、B、D、E、F、C 中序中序: D、B、E、F、A、C 前序前序: A、B、D、E、F、C 中序中序: D、B、E、F、A、C 前序前序: B、D、E、F 中序中序: D、B、E、F 前序前序: E、F 中序中序: E、FABCDEF下面的算法是按先序建立二叉树的二叉链表过

21、程下面的算法是按先序建立二叉树的二叉链表过程. .Void CreateBiTree(BiTree Void CreateBiTree(BiTree * *T) T) char ch; char ch; scanf(“ %c ”,&ch); scanf(“ %c ”,&ch); if (ch=0) T = NULL; if (ch=0) T = NULL; else else if (!(T = (BiTNode if (!(T = (BiTNode* *)malloc(sizeof(BiTNode) return 0; )malloc(sizeof(BiTNode) retu

22、rn 0; T-data = ch; / T-data = ch; / 生成根结点生成根结点 CreateBiTree(T-lchild); / CreateBiTree(T-lchild); / 构造左子树构造左子树 CreateBiTree(T-rchild); / CreateBiTree(T-rchild); / 构造右子树构造右子树 return 1; / CreateBiTree return 1; / CreateBiTreeABCDEFGA BC DEF G 图图6-18 建立二叉树的二叉链表建立二叉树的二叉链表(a) 二叉树二叉树(b) 建立的二叉链表建立的二叉链表算法如下：算法如下：Int sum( BiTree *T) if (T=NULL)