第5章树和二叉树4.ppt

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

1、第5章 树和二叉树,第5章 树和二叉树,5.1 树的概念和基本操作5.2 二叉树 5.3 树和森林5.4 哈夫曼树及其应用5.5 应用举例,5.4.1 哈夫曼树的基本概念5.4.2 哈夫曼树的构造算法5.4.3 哈夫曼编码5.4.4 哈夫曼编码的算法实现,5.4 最优二叉树哈夫曼树,5.4.1 哈夫曼树的基本概念1.路径:从树中一个结点到另一个结点之间的分支构成两个结点之间的路径.2.路径长度:是指从根结点到该结点的路径上分支的数目。3.树的路径长度:从树根到每个结点的路径长度之和。完全二叉树就是这种路径长度最短的二叉树.,4.结点的带权路径长度：是从该结点到树根之间的路径长度与结点上权值的乘

2、积.5.树的带权路径长度：树中所有叶子结点的带权路径长度之和.通常记作:nWPL=wklk k=1,其中：Wk：第k个叶子结点的权值；Lk：第k个叶子结点的路径长度.,6.哈夫曼树（最优二叉树）是指对于一组带有确定权值的叶子结点构造的具有最小带权路径长度的二叉树。即：设有给定的 n 个权值 w1,w2,wn，构造一棵由 n个叶子结点的,每个叶子结点的带权为 wi,则其中带权路径长度 WPL最小的二叉树称为最优树或哈夫曼树.,WPL=72+52+23+43+92=60,WPL=74+94+53+42+21=89,根据给定的 n 个权值 w1,w2,wn，构造 n 棵二叉树的集合 F=T1,T2,

3、Tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点,其左、右子树为空树;,5.4.2 哈夫曼树的构造,(1),(哈夫曼算法)以二叉树为例:,在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;,(2),从F中删去这两棵树，同时加入 刚生成的新树;,重复(2)和(3)两步，直至 F 中只 含一棵树为止。,(3),(4),例如:已知权值 W=8,6,2,4 构造哈夫曼树的过程,4,8,6,2,8,6,第一步:,第二步:,第三步:,图5-23 构造哈夫曼树的过程,第四步:,图5-23 构造哈夫曼树

4、的过程,由哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越靠远离根结点。,在构造哈夫曼树时，可设置一个结构数组HuffNode保存各结点的信息，数组HuffNode的大小为：2n-1,数组元素的结构形式：,5.4.2 哈夫曼树的构造算法,结点的权值,1.前缀编码在电报传送的过程中,传送的电文以二进制代码作为电报编码.例如:电文:“ABAACCBADCA”,电文中只含四个字符:A,B,C,D,每个字符用两位定长编码,例如：A:00;B:01;C:10;D:11.则上述电文可译为:0001000010100100111000 A B AA

5、CC B A D C A总长22位,接收方按两位一组译码即可.,5.4.3 哈夫曼编码,由于采用定长编码的电文总长无法缩短,因此,对字符采用不定长编码.且让电文中出现次数较多的字符采用尽可能短的编码,从而尽可能的减小电文总长.例如:上例中,A,C出现的频率较高,对A,B,C,D的编码分别为:0,00,1,01,则电文总长:14位的二进制串:“00000110000110”,长度缩短了但译码出现的困难.前缀编码:是指任何一个字符的编码都不是另一个字符编码的前缀.,2.哈夫曼编码以每种字符在电文中出现的次数为Wi,其编码长度为li,电文中可能出现的字符有n种,则电文总长为:nWPL=wili i=

6、1正好是对应的哈夫曼树的WPL.因此以哈夫曼树来设计的二进制前缀编码使得电文总长最短.,具体设计如下:将可能出现的字符作为叶子结点,电文中字符出现的频率为各个叶子结点的权值,设计一棵哈夫曼树,树的左分支表示二进制数0，右分支表示二进制数1,则从根结点到每一个叶子结点（字符）的路经上分支字符组成的字符串，即为该字符的二进制前缀编码,又称为哈夫曼编码.例如:字符A,B,C,D出现的频率为0.4,0.2,0.3,0.1则得到如图所示的哈夫曼树及哈夫曼编码。,哈夫曼编码：A：0C：10B：110D：111,(a)字符出现的频率,(b)哈夫曼树,图5-24 哈夫曼编码设计示例,第一步:,第二步:,第三步

7、:,图5-25 构造哈夫曼树并设计编码,例如:已知权值 W=5,6,2,9,7 构造哈夫曼树并设计哈夫曼编码,补充习题,1.一棵哈夫曼树有个m叶子结点,则其结点总数为_.2.设电文中出现的字母为A，B，C，D和E，每个字母在电文中出现的次数分别是6，23，3，5，和12，按哈夫曼编码，则字母C的编码应是（）A10 B.110 C.1110 D.11113.设给定权集W=2，3，4，7，8，9，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL.,4.有一份电文中共使用5个字符：a,b,c,d,e,他们的出现频率依次为4，7，5，2，9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树

8、根结点的权的次序构造），并求出每个字符的哈夫曼编码。5.如下图所示,以数据集4，5，6，7，10，12，18为结点权值所构成的哈夫曼树为_，其带权路径长度为_。,5.5 应用举例,1、查询二叉树中某个结点,2、统计二叉树中叶子结点的个数,3、求二叉树的深度(后序遍历),4、由前序+中序序列构造二叉树,5、创建二叉树的二叉链表存储,1).在二叉树不空的前提下,和根结点的元素进行比较,若相等,则找到返回 该结点;,2).否则在左子树中进行查找,若找到,则返回该结点;,3).否则继续在右子树中进行查找,若找到,则返回该结点,否则返回空。,1、查询二叉树中某个结点,分三步进行:,BiTree sear

9、ch(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、统计二叉树中叶子结点的个数,算法基本思想:,中序遍历二叉树，在遍历过程中查找叶子结点，并计数。因此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为:若是叶子结点，则计数器增1。分三种

10、情况:1)二叉树为空,则叶子结点数为0.2)若只一个根结点,则叶子结点数为1.3)若二叉树非空,分别统计左,右子树中叶子结点数.,void CountLeaf(BiTree*bt,int count)if(bt!=NULL)if(!bt-lchild)/if/CountLeaf,int CountLeaf(BiTree T)/返回指针T所指二叉树中所有叶子结点个数 if(!T)return 0;/二叉树为空 if(!T-lchild/else/CountLeaf,3、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别

11、求得左、右子树的深度，算法中“访问结点”的操作为:求得左、右子树深度的最大值，然后加 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、二叉树的确定,前序（后序）中序 唯一确定一棵二叉树 例:,前序:A、B、D、E、F

12、、C 中序:D、B、E、F、A、C,确定过程:1、确定根 A;2、在中序序列中找到 A;3、中序序列中的 A 的左部为 A 的左子树上的所有结点,A 的右部为 A 的右子树中的所有结点;4、根据 A 的左子树的所有结点的前序序列确定 A 的左子树的根节点，它是 A 的左儿子;5、根据 A 的右子树的所有结点的前序序列确定 A 的右子树的根节点，它是 A 的右儿子;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、

13、F 中序:E、F,A,B,C,D,E,F,下面的算法是按先序建立二叉树的二叉链表过程.Void CreateBiTree(BiTree*T)char ch;scanf(“%c”,/CreateBiTree,5.5 建立二叉树的算法,B,C,D,E,F,G,图6-18 建立二叉树的二叉链表,(a)二叉树,(b)建立的二叉链表,习题12 统计二叉树中结点的总数,算法如下：Int sum(BiTree*T)if(T=NULL)return(0);else return(sum(T-lchild)+sum(T-rchild)+1),习题14 编写算法判别任一二叉树是否为满二叉树,分析：满二叉树的特征：任何结点或者为叶子结点，或者有左右两棵子树。算法如下：Int full(BiTree*T)if(T!=NULL)if(T-lchild=NULL),本章小结,通过本的学习，应掌握以下要点：1.理解并熟练掌握二叉树的定义、二叉树的性质；2.熟练掌握遍历二叉树的三种遍历算法：先序、中序、后序；遍历二叉树是二叉树各种操作的基础，灵活运用遍历算法实现二叉树的其它操作。3.熟练掌握树、森林与二叉树的转换方法、以树的遍历。4.掌握哈夫曼树的相关概念、构造哈夫曼树的方法以及哈夫曼编码的方法。5.学会编写实现树的各种操作的算法.,