收藏 分销(赏)

C语言-第六章-树.ppt

上传人:仙人****88 文档编号:14753192 上传时间:2026-11-13 格式:PPT 页数:89 大小:802KB 下载积分:10 金币
下载 相关
C语言-第六章-树.ppt_第1页
第1页 / 共89页
C语言-第六章-树.ppt_第2页
第2页 / 共89页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章,树和二叉树,本章中主要介绍下列内容:,树的逻辑定义和存储结构,二叉树的逻辑定义、存储结构,二叉树的基本操作算法,树和二叉树的转换,哈夫曼树及其应用,退出,5.1,树,的概念与定义,5.2,二叉树,5.3,树与森林,5.4,哈夫曼树及其应用,5.5,应用举例,5.1,树,树型结构是一类重要的非线性结构。树型结构是结点之间有分支,并且具有层次关系的结构,它非常类似于自然界中的树。树结构在客观世界国是大量存在的,例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用,例如在编译程序中,用树来表示源程序的语法结构;在数据库系统中,可用树来组织信息;在分析算法的行为时,可用树来描述其执行过程。等等。,5.1,树,5.1.1,树的定义和基本运算,1.,定义,树是一种常用的非线性结构。我们可以这样定义:,树,是,n,(,n0,),个结点的有限集合。若,n=0,,,则称为,空树,;否则,有且仅有一个特定的结点被称为,根,,当,n1,时,其余结点被分成,m,(,m0,),个互不相交的子集,T1,,,T2,,,.,,,Tm,,,每个子集又是一棵树。由此可以看出,树的定义是递归。,树,(Tree),:,是包括,n(n=0),个,结点,的有限集,T,。当,T,非空时,满足:,(,1,)有且仅有一个特别标出的称为,根,的 结点;,(,2,),除,根结点,外,其余结点可分为,m,(,m=0,),个互不相交非空的有限集,T,1,T,2,T,m,其中,每一个集合本身又是一棵树,称为根的,子树,(,Subtree,),。,树的递归定义:,空树,:不包括任何结点的树。,树结构的特点:,(,1,)树的根的结点没前驱结点,除了根结点之外,的所有结点都有且只有一个前驱结点;,(,2,)树的结点可以有零个或多个后继结点。,树结构描述的是层次关系。,A,只有根结点的树,A,B,C,D,E,F,G,H,I,J,K,L,M,有子树的树,根,子树,树的表示方法:,(c),凹入表,(,a,),树形表示,A,B,C,D,E,F,I,J,G,H,(A(B(D)(E(I)(J)(C(G)(H),(d),嵌套括号表示法,C,D,E,I,J,F,G,H,A,B,(b),文氏图,对比,树型结构,和,线性结构,的结构特点,线性结构,树型结构,第一个数据元素,(,无前驱,),根结点,(,无前驱,),最后一个数据元素,(,无后继,),多个叶子结点,(,无后继,),其它数据元素,(,一个前驱、,一个后继,),其它数据元素,(,一个前驱、,多个后继,),基本术语,结点,(node),表示树中的元素,包括数据项及若干指向其子树的分支,结点的度,(degree),结点拥有的子树数,叶子,(leaf),度为,0,的结点,又叫,终端结点,孩子,(child),结点子树的根称为该结点的孩子,双亲,(parents),孩子结点的上层结点叫该结点的,树的度,一棵树中最大的结点度数,结点的层次,(level),从根结点算起,根为第一层,它的孩子为第二层,深度,(depth),树中结点的最大层次数,有序树、无序树,如果树中每棵子树从左向右的排列拥 有一定的顺 序,不得互换,则称为有序树,否则称为无序树。,森林,是,m,(,m,0,),棵互不相交的树的集合。,在树结构中,结点之间的关系又可以用家族关系描述,定义如下:,孩子、双亲,结点子树的根称为这个结点的孩子,而这个结点又被称为孩子的双亲。,子孙,以某结点为根的子树中的所有结点都被称为是该结点的子孙。,祖先,从根结点到该结点路径上的所有结点。,兄弟,同一个双亲的孩子之间互为兄弟。,堂兄弟,双亲在同一层的结点互为堂兄弟。,A,B,C,D,E,F,G,H,I,J,K,L,M,结点,A,的度:,3,结点,B,的度:,2,结点,M,的度:,0,叶子:,K,,,L,,,F,,,G,,,M,,,I,,,J,结点,A,的孩子:,B,,,C,,,D,结点,B,的孩子:,E,,,F,结点,I,的双亲:,D,结点,L,的双亲:,E,结点,B,,,C,,,D,为兄弟,结点,K,,,L,为兄弟,树的度:,3,结点,A,的层次:,1,结点,M,的层次:,4,树的深度:,4,结点,F,,,G,为堂兄弟,结点,A,是结点,F,,,G,的祖先,2.,树的基本运算,常用操作:,(,1,),Initiate,(,t,),初始化一棵空树,t,。,(,2,),Root,(,x,),求结点,x,所在树的根结点。,(,3,),Parent,(,t,,,x,),求树,t,中结点,x,的双亲结点。,(,4,),Child,(,t,,,x,,,i,),求树,t,中结点,x,的第,i,个孩子结点。,(,5,),RightSibling,(,t,,,x,),求树,t,中结点,x,的第一个右边兄弟结点。,(,6,),Insert,(,t,,,x,,,i,,,s,),把以,s,为根结点的树插入到树,t,中作为结点,x,的第,i,棵子树。,(,7,),Delete,(,t,,,x,,,i,),在树,t,中删除结点,x,的第,i,棵子树。,(,8,),Traverse,(,t,),是树的遍历操作,5.2,二叉树,5.2.1,二叉树的定义和基本运算,1.,定义,定义:,二叉树,是另一种树形结构。它与树形结构的区别是:,(,1,)每个结点最多有两棵子树;,(,2,)子树有左右之分。,二叉树也可以用递归的形式定义。即:二叉树是,n,(,n,0,),个结点的有限集合。当,n=0,时,称为空二叉树;当,n0,时,有且仅有一个结点为二叉树的根,其余结点被分成两个互不相交的子集,一个作为左子集,另一个作为右子集,每个子集又是一个二叉树。,图,5-6,G H,D E F,B C,A,二叉树的,5,种形态:,图,5-7,(a),(b),(c),(d),(e),A,只有根结点,的二叉树,空二叉树,A,B,右子树为空,A,B,左子树为空,A,B,C,左、右子树,均非空,二叉树性质,性质,1,:,证明:用归纳法证明之,i=1,时,只有一个根结点,是对的,假设对所有,j(1,ji),命题成立,即第,j,层上至多有 个结点,那么,第,i-1,层至多有 个结点,又二叉树每个结点的度至多为2,第,i,层上最大结点数是第,i-1,层的2倍,即,故命题得证,性质,2,:深度为,k,的二叉树至多有,个结点(,k,1),证明:由性质,1,,可得深度为,k,的二叉树最大结点数是,【,性质,3,】,对于任意一棵二叉树,BT,,,如果度为,0,的结点个数为,n,0,,,度为,2,的结点个数为,n,2,,则,n,0,=n,2,+1,。,证明:,1,、结点总数为度为,0,的结点加上度为,1,的结点再加上度,为,2,的结点:,n=n0+n1+n2,2,、另一方面,二叉树中一度结点有一个孩子,二 度结,点有二个孩子,根结点不是任何结点的孩子,因此,,结点总数为:,n=n1+2n2+1,3,、两式相减,得到:,n0=n2+1,特殊形式的二叉树,满二叉树,定义:,特点:每一层上的结点数都是最大结点数,完全二叉树,定义:深度为,k,,,有,n,个结点的二叉树当且仅当其每一个结点都与深度为,k,的满二叉树中编号从1至,n,的结点一一对应时,称为,特点,叶子结点只可能在层次最大的两层上出现,对任一结点,若其右分支下子孙的最大层次为,l,,,则其左分支下子孙的最大层次必为,l,或,l+1,1,2,3,11,4,5,8,9,12,13,6,7,10,14,15,1,2,3,11,4,5,8,9,12,6,7,10,1,2,3,4,5,6,7,1,2,3,4,5,6,【,性质,4,】,具有,n,个结点的完全二叉树的深度为,log,2,n,+1,。,其中,,log,2,n,的结果是不大于,log,2,n,的最大整数。,证明:假设具有,n,个结点的完全二叉树的深度为,K,,,则根据性质,2,可以得出:,2,K-1,-1n2,K,-1,将不等式两端加,1,得到:,2,K-1,n2,K,将不等式中的三项同取以,2,为底的对数,并经过化简后得到:,K-1log,2,n1,,,则其双亲是,i/2,如果2,in,,,则结点,i,无左孩子;如果2,in,,,则其左孩子是2,i,(3),如果2,i+1n,,,则结点,i,无右孩子;如果2,i+1n,,,则其右孩子是2,i+1,2.,二叉树的基本运算,(1)Initiate,(,bt,),建立一棵,(,2,),Create,(,x,,,lbt,,,rbt,),生成一棵以,x,为根结点的数据域信息,以二叉树,lbt,和,rbt,为左子树和右子树的二叉树。,(,3,),InsertL,(,bt,,,x,,,parent,),将数据域信息为,x,的结点插入到二叉树,bt,中作为结点,parent,的左孩子结点。如果结点,parent,原来有左孩子结点,则将结点,parent,原来的左孩子结点作为结点,x,的左孩子结点。,(4,),InsertR,(,bt,,,x,,,parent,),将数据域信息为,x,的结点插入到二叉树,bt,中作为结点,parent,的右孩子结点。如果结点,parent,原来有右孩子结点,则将结点,parent,原来的右孩子结点作为结点,x,的右孩子结点。,(,5,),DeleteL,(,bt,,,parent,),在二叉树,bt,中删除结点,parent,的左子树。,(,6,),DeleteR,(,bt,,,parent,),在二叉树,bt,中删除结点,parent,的右子树。,(,7,),Search,(,bt,,,x,),在二叉树,bt,中查找数据元素,x,。,(,8,),Traverse,(,bt,),按某种方式遍历二叉树,bt,中的全部结点。,5.2.3,二叉树的存储结构,二叉树也可以采用两种存储方式:顺序存储结构和链式存储结构。,1.,顺序存储结构,这种存储结构适用于完全二叉树。其存储形式为:用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构。,图,5-11,8,4 5 6 7,2 3,1,二叉树的顺序存储表示可描述为:,#define MAXNODE /*,二叉树的最大结点数*,/,typedef,elemtype,SqBiTreeMAXNODE,/*1,号单元存放根结点*,/,SqBiTree,bt,;,即将,bt,定义为含有,MAXNODE,个,elemtype,类型元素的一维数组,。,对于一般二叉树,则应将其每个结点与完全二叉树上的结点相对照,存储在一维数组的相应分量中。,图,514,一般二叉树及其顺序表示,3,2,链式存储结构,在顺序存储结构中,利用编号表示元素的位置及元素之间孩子或双亲的关系,因此对于非完全二叉树,需要将空缺的位置用特定的符号填补,若空缺结点较多,势必造成空间利用率的下降。在这种情况下,就应该考虑使用链式存储结构。,常见的二叉树结点结构如下所示:,图,5-12,Lchild,Data,Rchild,其中,,Lchild,和,Rchild,是分别指向该结点左孩子和右孩子的指针,,item,是数据元素的内容。在,C,语言中的类型定义为:,typedef,char,elemtype,;,typedef,struct,BTNode,elemtype,data;,struct,BTNode,*,lchild,;*,rchild,;/*,左右孩子指针*,/,BTNode,*,BTree,;,下面是一棵二叉树及相应的链式存储结构。,图,5-13,G H,D E F,B C,A,G H ,D E F ,B C,A,BT,在,n,个结点的二叉链表中,有,n+1,个空指针域,这种存储结构的特点是寻找孩子结点容易,双亲比较困难。因此,若需要频繁地寻找双亲,可以给每个结点添加一个指向双亲结点的指针域,其结点结构如下所示。,图,5-14,有关二叉树在链式存储结构下的操作算法将在随后介绍。,Lchild,Data,Rchild,Parent,A,B,C,D,E,F,G,A,B,C,D,E,F,G,5.2.4,遍历二叉树,二叉树是一种非线性的数据结构,在对它进行操作时,总是需要逐一对每个数据元素实施操作,这样就存在一个操作顺序问题,由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。,二叉树的遍历方式分为两大类:一类按根、左子树和右子树三个部分进行访问;另一类按层次访问。下面我们将分别进行讨论。,1.,按根、左子树和右子树三部分进行遍历,遍历二叉树的顺序存在下面,6,种可能:,TLR,(,根左右),TRL,(,根右左),LTR,(,左根右),RTL,(,右根左),LRT,(,左右根),RLT,(,右左根),其中,,TRL,、,RTL,和,RLT,三种顺序在左右子树之间均是先右子树后左子树,这与人们先左后右的习惯不同,因此,往往不予采用。余下的三种顺序,TLR,、,LTR,和,LRT,根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。,二叉树的遍历,先(根)序的遍历算法:,若二叉树为空树,则空操作;否则,(,1,)访问根结点;,(,2,)先序遍历左子树;,(,3,)先序遍历右子树。,中(根)序的遍历算法:,若二叉树为空树,则空操作;否则,(,1,)中序遍历左子树;(,2,)访问根结点;(,3,)中序遍历右子树。,后(根)序的遍历算法:,若二叉树为空树,则空操作;否则,(,1,)后序遍历左子树;(,2,)后序遍历右子树;(,3,)访问根结点。,G H,D E F,B C,A,先序序列:,中序序列:,后序序列:,图,5-15,ABDGCEFH,DGBAECHF,GDBEHFCA,由二叉树的中序以及先序或者后序中的一种遍历序列可唯一地确定一棵二叉树。例,先序序列,ABHFDECKG,和中序序列,HBDFAEKCG,构造二叉树过程如下:,练习,:,已知一棵二叉树的先序遍历为,1,,,2,,,3,,,4,,,5,,,6,,,7,,,8,,,9,分别画出当中序遍历为,3,,,2,,,5,,,4,,,1,,,6,,,8,,,7,,,9,以及,中序遍历为,4,,,3,,,5,,,2,,,1,,,7,,,6,,,8,,,9,的二叉树,由此可以看出:,(,1,)遍历操作实际上是将非线性结构线性化的过程,其结果为线性序列,并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列;,(,2,)遍历操作是一个递归的过程,因此,这三种遍历操作的算法可以用递归函数实现。,(,1,)先序遍历递归算法,void,PreOrder,(,BTree,bt,),/*,先序遍历二叉树,bt,*/,if(,bt,=NULL)return;/*,递归调用的结束条件*,/,Visit,(,bt,-data,),;/*,访问结点的数据域*,/,PreOrder,(,bt,-,lchild,),;/*,先序递归遍历,bt,的左子树*,/,PreOrder,(,bt,-,rchild,),;/*,先序递归遍历,bt,的右子树*,/,(,2,),中序遍历递归算法,void,InOrder,(,BTree,bt,),/*,中序遍历二叉树,bt,*/,if(,bt,=NULL)return;/*,递归调用的结束条件*,/,InOrder,(,bt,-,lchild,),;/*,中序递归遍历,bt,的左子树*,/,Visit,(,bt,-data,),;/*,访问结点的数据域*,/,InOrder,(,bt,-,rchild,),;/*,中序递归遍历,bt,的右子树*,/,(,3,),后序遍历递归算法,void,PostOrder,(,BTree,bt,),/*,后序遍历二叉树,bt,*/,if(,bt,=NULL)return;/*,递归调用的结束条件*,/,PostOrder,(,bt,-,lchild,),;/*,后序递归遍历,bt,的左子树*,/,PostOrder,(,bt,-,rchild,),;/*,后序递归遍历,bt,的右子树*,/,Visit,(,bt,-data,),;/*,访问结点的数据域*,/,2.,按层次遍历二叉树,实现方法为从上层到下层,每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。,G H,D E F,B C,A,图,5-19,按层次遍历该二叉树的序列为:,ABCDEFGH,二叉树用顺序存储结构表示时,按层遍历的算法实现,A 1,B 2 3 C,D 4 5 E F 6 7 G,(a),A 1,B 2 3 C,D 4 E 6 7 F,(b),图,5-20,0,1,2,3,4,5,6,7,A,B,C,E,F,#,D,void,LevelOreder(QBTree,BT),for(i=1;idata);,if(qfront,-,lchild,!=NULL),rear+;,qrear,=,qfront,-,lchild,;,if(qfront,-,rchild,!=NULL),rear+;,qrear,=,qfront,-,rchild,;,5.3,树的存储结构,树的存储结构,双亲表示法,实现:定义结构数组存放树的结点,每个结点含两个域:,数据域:存放结点本身信息,双亲域:指示本结点的双亲结点在数组中位置,特点:找双亲容易,找孩子难,typedef,struct,node,datatype,data;,int,parent;,JD;,JD tM;,a,b,c,d,e,f,h,g,i,a,c,d,e,f,g,h,i,b,0,1,2,2,3,5,5,5,1,0,9,6,0,1,2,3,4,5,7,8,9,data,parent,0,号单元不用或,存结点个数,如何找孩子结点,孩子表示法,多重链表:每个结点有多个指针域,分别指向其子树的根,结点同构:结点的指针个数相等,为树的度,D,结点不同构:结点指针个数不等,为该结点的度,d,data child1 child2 .,childD,data degree child1 child2 .,childd,孩子链表:每个结点的孩子结点用单链表存储,再用含,n,个元素的结构数组指向每个孩子链表,孩子结点:,typedef,struct,node,int,child;/,该结点在表头数组中下标,struct,node *next;/,指向下一孩子结点,JD;,表头结点:,typedef,struct,tnode,datatype,data;/,数据域,struct,node *,fc,;/,指向第一个孩子结点,TD;,TD tM;/t0,不用,a,b,c,d,e,f,h,g,i,6,0,1,2,3,4,5,7,8,9,a,c,d,e,f,g,h,i,b,data,fc,2,3,4,5,9,7,8,6,如何找双亲结点,带双亲的孩子链表,6,1,2,3,4,5,7,8,9,a,c,d,e,f,g,h,i,b,data,fc,2,3,4,5,9,7,8,6,0,1,2,2,3,5,5,5,1,parent,a,b,c,d,e,f,h,g,i,孩子兄弟表示法(二叉树表示法),实现:用二叉链表作树的存储结构,链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点,特点,操作容易,破坏了树的层次,typedef,struct,node,datatype,data;,struct,node *,fch,*,nsib,;,JD;,a,b,c,d,e,f,h,g,i,a,b,c,d,e,f,g,h,i,树、森林与二叉树的转换,树、森林转换为二叉树,由于树和二叉树都可以用二叉链表作存储结构,则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系。,从二叉链表表示的定义可知,任何一棵和树对应的二叉树,其右子树必空。这样,若把森林中第二棵树的根结点看成是第一棵树的兄弟,则可以导出森林和二叉树之间的对应关系。,树、森林与二叉树的转换,一、树转换为二叉树,转换规则:,步骤:,1.,将同父亲的兄弟结点连接;,2.,对每一个非叶结点只保留第一个孩子链,删除其他孩子的链;,3.,将树向左旋转,45,0,。,树转换为二叉树,事例,A,B,E,D,C,H,J,I,G,F,A,B,E,D,C,H,J,I,G,F,树转换为二叉树,事例,A,B,E,D,C,H,J,I,G,F,A,B,E,D,C,H,J,I,G,F,二、森林转换成二叉树,二、森林转换为二叉树,转换规则:,如果,F,T,1,T,2,T,m,是森林,则可按如下规则转换成一棵二叉树,B,root,LB,RB,。,(,1,)若,F,为空,则,B,为空树;,(,2,)若,F,非空,则,B,的根,root,为森林中第一棵树的根,Root(T,1,),,,B,的左子树,LB,是从,T,1,中根结点的子树森林,F,1,T,11,T,12,T,1m1,转换而成的二叉树;其右子树,RB,是从森林,F,T,2,T,3,T,m,转换而成的二叉树。,A,B,E,G,C,D,F,H,I,A,B,E,G,C,D,F,H,I,A,B,E,G,C,D,F,H,I,森林转换 成二叉树,3,、二叉树转换为树,转换规则:,1.,对有左子树的所有结点与其左孩子的右链上的所有结点进行连接;,2.,删除以前所有的旧右链。,A,B,E,D,C,H,J,I,G,F,A,B,E,D,C,H,J,I,G,F,4,、二叉树转换成森林,转换规则:,如果,B,root,LB,RB,是一棵二叉树,则可按如下规则转换成森林,F,T,1,T,2,T,m,(,1,)若,B,为空,则,F,为空树;,(,2,)若,B,非空,则为森林中第一棵树的根,Root,(,T,1,),即为,B,的根,root,,,T,1,中根结点的子树森林,F,1,T,11,T,12,T,1m1,是有,B,的左子树,LB,转换而来的森林;,F,中除,T,1,之外的其余树组成的森林,F,T,2,T,3,T,m,是由,B,的右子树转换而成的。,二叉树转换成森林,示例,A,B,C,F,D,G,E,H,I,A,B,C,F,D,G,E,H,I,树、森林与二叉树的转换关系,树转换为二叉树特点:一棵树转换成二叉树后,该二叉树根结点没有右孩子。,由树与二叉树的对应关系特点可得,:,右图该二叉树就不能转化为树,.,树的集合,小于二叉树的集合,.,二叉树与森林才是一一对应的,.,A,B,E,D,C,G,F,5.3.3,树和森林的遍历,1.,遍历,的定义,:,按某一规律系统的,访问,树中的所有,结点,并使每个结点恰好被,访问,一次。,2.,遍历的方法:按深度方向和按宽度方向遍历。,(,I,),按深度方向(以右图为例),a.,先根次序,b.,后根次序,a.,先根次序,(1,2,3,5,8,9,6,10,4,7),(,1,)访问根结点;,(,2,)从左到右按先根次序遍历根结点的每棵子树。,b.,后根次序,(2,8,9,5,10,6,3,7,4,1),(,1,)从左到右按后根次序遍历根结点的每棵子树,;,(,2,)访问根结点。,(,II,),按宽度方向遍历,先访问层数为,0,的结点,然后从左到右逐个访,问层数为,1,的结点,依此类推,直到访问完树中,的全部结点。,层次序列(,1,,,2,,,3,,,4,,,5,,,6,,,7,,,8,,,9,,,10,),1.,先序遍历,:(1),先访问森林中第一棵树的根结点,(2),先序遍历第一棵树中根结点的子树森林,(3),先序遍历除去第一课树之后剩余的树构成的森林,后序遍历,:(1),后序遍历森林中第一棵树的根结点的子树森林,(2),访问第一棵树的根结点,(3),后序遍历除去第一课树之后剩余的树构成的森林,森林的遍历,1.,先序遍历,:,(,A,B,C,K,D,E,H,F,J,G),后序遍历,:(B,K,C,A,H,E,J,F,G,D),哈夫曼树与哈夫曼编码,一、最优二叉树的定义,结点的路径长度,:从根结点到该结点的路径上分支的数目。,树的路径长度,:树中每个叶结点的路径长度之和。,具有不同路径长度的二叉树,一、最优二叉树的定义,树的带权路径长度,:树中所有叶子结点的带权路径长度之和,WPL(T)=,w,k,l,k,(,对所有叶子结点,),。,其中,W,k,为叶子结点的权值,l,k,为叶子结点的路径长度,.,具有不同带权路径长度的二叉树,2,7,9,7,5,4,9,2,WPL(T)=7,2+52+23+43+92 =60,WPL(T)=7,4+94+53+42+21 =89,5,4,最优二叉树又称哈夫曼树,是指权值为,w1,w2,wn,的,n,个叶子结点的二叉树中带权路径长度最小的二叉树。,如下图所示,,(c),二叉树是这,4,个带权叶子结点的哈夫曼树。,在哈夫曼树中,权值大的结点离根最近。,哈夫曼树与哈夫曼编码,二、如何构造最优二叉树,哈夫曼最早研究出一个带有一般规律的算法,:,(1),根据给定的,n,个权值,w,1,w,2,w,n,,,构造,n,棵二叉树的集合,F,=T,1,T,2,T,n,,,其中每棵二叉树中均只含一个带权值为,w,i,的根结点,其左、右子树为空树;,(2),在,F,中选取其根结点的权值为,最小,的两棵二叉树,分别作为左、右子树构造一棵新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和,;,(3),从,F,中删去这两棵树,同时加入刚生成的新树,;,(4),重复,(2),和,(3),两步,直至,F,中只含一棵树为止。,哈夫曼树与哈夫曼编码,二、如何构造最优二叉树,a,7,b,5,c,2,d,9,e,3,f,11,g,1,h,6,c,2,g,1,3,e,3,6,b,5,11,h,6,a,7,13,d,9,20,f,11,24,44,哈夫曼树与哈夫曼编码,三,.,哈夫曼编码,在远程通讯中,要将待传字符转换成由二进制组成的字符串:,设要传送的字符为:,ABACCDA,若编码为:,A00,B01,C10,D-11,00,01,00,10,10,11,00,若将编码设计为长度不等的二进制编码,即让待传字符串中,出现次数较多的字符采用尽可能短的编码,,则转换的二进制字符串便可能减少。,哈夫曼树与哈夫曼编码,在远程通讯中,要将待传字符转换成由二进制的字符串:,设要传送的字符为:,ABACCDA,若编码为:,A0,B00,C1,D-01,0000,11010,但:,0000,AAAA ABA BB,重码,关键:,要设计长度不等的编码,则必须使任一字符的编码都不是另一个字符的编码的前缀。,哈夫曼树与哈夫曼编码,设要传送的字符为:,ABACCDA,若编码为:,A0,B110,C10,D-111,0,110,0,10,10,111,0,A,C,B,D,0,0,0,1,1,1,采用二叉树设计二进制前缀编码,哈夫曼树与哈夫曼编码,译码过程,:分解接收字符串:遇“,0”,向左,遇“,1”,向右;一旦到达叶子结点,则译出一个字符,反复由根出发,直到译码完成。,A,C,B,D,0,0,0,1,1,1,0,110,0,10,10,111,0,ABACCDA,哈夫曼树与哈夫曼编码,在一个字符集中,任何一个字符的编码都不是另一个字符编码的前缀,这种编码称为,前缀编码,。,我们可以利用二叉树来设计二进制的前缀编码。约定左分支表示字符,0,,右分支便是字符,1,,则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码也是前缀编码。,证明:,假设某一个叶子,x,结点的编码是另一个叶子结点,y,编码的前缀,说明从根结点到叶子结点,y,中间需经过结点,x,,,从而说明,x,有左或右子树,这与,x,是叶子结点矛盾。,那么现在求最短的二进制编码实际上就是构造哈夫曼树的过程,由此得到的二进制编码,称,哈夫曼编码,。,哈夫曼树与哈夫曼编码,由于哈夫曼树中没有度为,1,的结点,(,这类树又称严格的,(strict)(,或正则的,),二叉树,),;则一棵有,n,个叶子结点的赫夫曼树共有,2n-1,个结点(因,n,2,=n,0,-1),,,可以存储在一个大小为,2n-1,的一维数组中。,如何选定结构类型?,(,1,)编码需要从叶子到根,(,2,)译码需要从根到叶子,求,Huffman,编码:由叶子,根,若:,(,1,)从左分支下去,则分支为“,0”,;,(,2,)从右分支下去,则分支为“,1”,。,c,2,g,1,3,e,3,6,b,5,11,h,6,a,7,13,d,9,20,f,11,24,44,1,0,1,0,0,0,0,0,0,1,1,1,1,1,哈夫曼树与哈夫曼编码,举例,例:已知某系统在通讯时,只出现,C,,,A,,,S,,,T,,,B,五种字符,它们出现的频率依次为,2,,,4,,,2,,,3,,,3,,试设计,Huffman,编码。,W,(,权),=2,,,4,,,2,,,3,,,3,,叶子结点个数,n=5,构造的,Huffman,树,14,8,4,6,4,2,2,0,0,0,1,1,1,3,3,0,1,T,B,A,C,S,哈夫曼树与哈夫曼编码,设计示例:,例:已知某系统在通讯时,只出现,C,,,A,,,S,,,T,,,B,五种字符,它们出现的频率依次为,2,,,4,,,2,,,3,,,3,,试设计,Huffman,编码。,由,Huffman,树得,Huffman,编码为:,14,8,4,6,4,2,2,0,0,0,1,1,1,3,3,0,1,T,B,A,C,S,出现频率越大的字符,其,Huffman,编码越短。,T B A C S,00 01 10 110 111,遍历算法的应用举例,:,1,、统计二叉树中叶子结点的个数,算法基本思想,:,先序,(,或中序或后序,),遍历二叉树,在遍历过程中查找叶子结点,并计数。,由此,需在遍历算法中增添一个,“,计数,”,的参数,并将算法中,“,访问结点,”,的操作改为,:,若是叶子,则计数器增,1,。,遍历算法的应用举例,:,统计二叉树中叶子结点的个数,(,先序遍历,),void,CountLeaf,(,BiTree,T,int,&count),if(T),if(!T-,lchild,)&(!T-,rchild,)count+;,CountLeaf,(T-,lchild,count);/,统计左子树中叶子结点个数,CountLeaf,(T-,rchild,count);/,统计右子树中叶子结点个数,遍历算法的应用举例,2,、求二叉树的深度,(,后序遍历,),算法基本思想,:,从二叉树深度的定义可知,二叉树的深度应为其左、右子树深度的最大值加,1,。由此,需先分别求得左、右子树的深度,算法中,“,访问结点,”,的操作为,:,求得左、右子树深度的最大值,然后加,1,。,首先分析,二叉树的深度,和它的,左,、,右子树深度,之间的关系。,遍历算法的应用举例,2,、求二叉树的深度,(,后序遍历,),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,;,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 通信科技 > 开发语言

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服