分享
分销 收藏 举报 申诉 / 100

类型数据结构(C++描述)_树.ppt

  • 上传人:xrp****65
  • 文档编号:13777279
  • 上传时间:2026-04-13
  • 格式:PPT
  • 页数:100
  • 大小:1,019KB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    数据结构 C++ 描述
    资源描述:
    单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第6章 树,数据结构(,C+,描述,),6.6 哈夫曼树,.树和森林,6.4线索二叉树,6.3遍历二叉树,6.2 二叉树,6.1 树的基本概念,退出,目录,6.1 树的基本概念,6.1.1 树的定义,1树的定义,树是由,n(n0),个结点组成的有限集合。若,n=0,,称为空树;若,n0,,则:,(1)有一个特定的称为根(,root),的结点。它只有直接后继,但没有直接前驱;,(2)除根结点以外的其它结点可以划分为,m(m0),个互不相交的有限集合,T,0,,T,1,,T,m-1,,,每个集合,T,i,(i=0,1,m-1),又是一棵树,称为根的子树,每棵子树的根结点有且仅有一个直接前驱,但可以有0个或多个直接后继。,由此可知,树的定义是一个递归的定义,即树的定义中又用到了树的概念。,树的结构参见图6-1。,在图6-1(,c),中,树的根结点为,A,,该树还可以分为三个互不相交子集,T,0,,T,1,,T,2,,,具体请参见图6-2,其中,T,0,=B,E,F,J,K,L,T,1,=C,G,T,2,=D,H,I,M,,其中的,T,0,,T,1,,T,2,都是树,称为图6-1(,C),中树的子树,而,T,0,,T,1,,T,2,又可以分解成若干棵不相交子树。如,T,0,可以分解成,T,00,,T,01,两个不相交子集,,T,00,=E,J,K,L,T,01,=F,,而,T,00,又可以分为三个不相交子集,T,000,,T,001,,T,002,,,其中,,T,000,=J,T,001,=K,T,002,=L。,2树的逻辑结构描述,一棵树的逻辑结构可以用二元组描述为:,tree=(k,R),k=,k,i,1in;n0,k,i,elemtype,R=r,其中,,n,为树中结点个数,若,n=0,,则为一棵空树,,n 0,时称为一棵非空树,而关系,r,应满足下列条件:,(1)有且仅有一个结点没有前驱,称该结点为树根;,(2)除根结点以外,其余每个结点有且仅有一个直接前驱;,(3)树中每个结点可以有多个直接后继(孩子结点)。,例如,对图6-1(,c),的树结构,可以二元组表示为:,K=A,B,C,D,E,F,G,H,I,J,K,L,M,R=r,r=(A,B),(A,C),(A,D),(B,E),(B,F),(C,G),(D,H),(D,I),(E,J),(E,K),(E,L),(H,M),3树的基本运算,树的基本运算可以定义如下几种:,(1),inittree,(&T),初始化树,T。,(2)root(T),求树,T,的根结点。,(3),parent(T,x),求树,T,中,值为,x,的结点的双亲。,(4),child(T,x,i),求树,T,中,值为,x,的结点的第,i,个孩子。,(5),addchild,(y,i,x),把值为,x,的结点作为值为,y,的结点的第,i,个孩子插入到树中。,(6),delchild,(x,i),删除值为,x,的结点的第,i,个孩子。,(7),traverse(T),遍历或访问树,T。,6.1.2,基本术语,1.结点,指树中的一个数据元素,一般用一个字母表示。,2.度,一个结点包含子树的数目,称为该结点的度。,3.树叶(叶子),度为0的结点,称为叶子结点或树叶,也叫终端结点。,4.孩子结点,若结点,X,有子树,则子树的根结点为,X,的孩子结点,也称为孩子,儿子,子女等。如图6-1(,c),中,A,的孩子为,B,C,D。,5.双亲结点,若结点,X,有子女,Y,,则,X,为,Y,的双亲结点。,6.祖先结点,从根结点到该结点所经过分枝上的所有结点为该结点的祖先,如图6-1(,c),中,M,的祖先有,A,D,H。,7.子孙结点,某一结点的子女及子女的子女都为该结点子孙。,8.兄弟结点,具有同一个双亲的结点,称为兄弟结点。,9.分枝结点,除叶子结点外的所有结点,为分枝结点,也叫非终端结点。,10层数,根结点的层数为1,其它结点的层数为从根结点到该结点所经过的分支数目再加1。,11.树的高度(深度),树中结点所处的最大层数称为树的高度,如空树的高度为0,只有一个根结点的树高度为1。,12.树的度,树中结点度的最大值称为树的度。,13.有序树,若一棵树中所有子树从左到右的排序是有顺序的,不能颠倒次序。称该树为有序树。,14.无序树,若一棵树中所有子树的次序无关紧要,则称为无序树。,15森林(树林),若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,6.1.3,树的表示,1树形结构表示法,具体参 见图6-1。,2.凹入法表示法,具体参见图6-3。,3.嵌套集合表示法,具体参 见图6-4。,4.广义表表示法,对图6-1(,c),的树结构,广义表表示法可表示为:,(,A(B(E(J,K,L),F),C(G),D(H(M),I),6.1.4,树的性质,性质1,树中的结点数等于所有结点的度加1。,证明:根据树的定义,在一棵树中,除根结点以外,每个结点有且仅有一个直接前驱,也就是说,每个结点与指向它的一个分支一一对应,所以,除根结点以外的结点数等于所有结点的分支数(即度数),而根结点无直接前驱,因此,树中的结点数等于所有结点的度数加1。,性质 2,度为,k,的树中第,i,层上最多有,k,i,-1,个结点(,i1)。,下面用数学归纳法证明:,对于,i=1,,显然成立,假设对于,i-1,层,上述条件成立,即第,i-1,层最多有,k,i,-2,个结点,,对于第,i,层,结点数最多为第,i-1,层结点数的,k,倍(因为度为,k),,故第,i,层的结点数为,k,i,-2,*k=,k,i,-1,。,性质3,深度为,h,的,k,叉树最多有 个结点。,证明:由性质2可知,若每一层的结点数最多,则整个,k,叉树结点数最多,共有 =,k,0,+k,1,+,k,h,-1,=,。,当一棵,K,叉树上的结点数达到 时,称为,满,K,叉树,。,性质4,具有,n,个结点的,k,叉树的最小深度为,log,k,(n(k-1)+1),。,(请注意,,x,表示取不小于,x,的最小整数,或叫做对,x,上取整。),证明:设具有,n,个结点的,k,叉树的深度为,h,,即在该树的前面,h-1,层都是满的,即每一层的结点数等于,k,i,-1,个(1,ih-1),,第,h,层(即最后一层)的结点数可能满,也可能不满,这时,该树具有最小的深度。由性质3知道,结点数,n,应满足下面条件:,n ,,通过转换为:,k,h,-1,n(k-1)+1,k,h,,,再取以,k,为底的对数后,可以得到:,h-1,log,k,(n(k-1)+1)h,,即有:,log,k,(n(k-1)+1)h0)。,可以用数学归纳法证明之。,性质2,深度(高度)为,k,的二叉树最大结点数为2,k,-1(k0)。,证明:深度为,k,的二叉树,若要求结点数最多,则必须每一层的结点数都为最多,由性质1可知,最大结点数应为每一层最大结点数之和。既为 2,0,+2,1,+2,k-1,=2,k,-1。,性质3,对任意一棵二叉树,如果叶子结点个数为,n,0,,,度为2的结点个数为,n,2,,,则有,n,0,=n,2,+1。,证明:设二叉树中度为1的结点个数为,n,1,,,根据二叉树的定义可知,该二叉树的结点数,n=n,0,+n,1,+n,2,。,又因为在二叉树中,度为0的结点没有孩子,度为1的结点有1 个孩子,度为2的结点有2个结孩子,故该二叉树的孩子结点数为,n,0,*0+n,1,*1+n,2,*2,,而一棵二叉树中,除根结点外所有都为孩子 结点,故该二叉树的结点数应为孩子结点数加1即:,n=n,0,*0+n,1,*1+n,2,*2+1,因此,有,n=n,0,+n,1,+n,2,=n,0,*0+n,2,*1+n,2,*2+1,,最后得到,n,0,=n,2,+1。,为继续给出二叉树的其它性质,先定义两种特殊的二叉树。,满二叉树,深度为,k,具有2,k,-1,个结点的二叉树,称为满二叉树。,从上面满二叉树定义可知,必须是二叉树的每一层上的结点数都达到最大,否则就不是满二叉树。,完全二叉树,如果一棵具有,n,个结点的深度为,k,的二叉树,它的每一个结点都与深度为,k,的满二叉树中编号为1,n,的结点一一对应,则称这棵二叉树为完全二叉树。,从完全二叉树定义可知,结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下,表示本层结点数达到最大后,才能放入下一层。从左到右,表示同一层结点必须按从左到右排列,若左边空一个位置时不能将结点放入右边。,从满二叉树及完全二叉树定义还可以知道,满二叉树一定是一棵完全二叉树,反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层,而完全二叉树的叶子结点可以分布在最下面两层。深度为4的满二叉树和完全二叉树如图6-6所示。,性质4,具有,n,个结点的完全二叉树高度为,log,2,(n),+1,或,log,2,(n+1),。,(,注意,x,表示取不大于,x,的最大整数,也叫做对,x,下取整,,x,表示取不小于,x,的最小整数,也叫做对,x,上取整。),证明:设该完全二叉树高度为,k,,则该二叉树的前面,k-1,层为满二叉树,共有2,k-1,-1,个结点,而该二叉具有,k,层,第,k,层至少至少有1个结点,最多有2,k-1,个结点。因此有下面的不等式成立:(2,k-1,1)+1 n(2,k-1,-1)+2,k-1,,,即有 2,k-1,n2,k,-1。,由式子后半部分可知,n2,k,-1,由式子前半部分可知 2,k-1,n,由有,n+12,k,,,同时取对数得:,log,2,(n+1)k,故,klog,2,(n+1),即,k=,log,2,(n+1),。,即得到第二个结论。,由有2,k-1,n,同时取对数得:,klog,2,n+1,即,k=,log,2,n,+1,即第一个结论成立,证毕。,性质5,如果将一棵有,n,个结点的完全二叉树从上到下,从左到右对结点编号1,2,,n,,然后按此编号将该二叉树中各结点顺序地存放于一个一维数组中,并简称编号为,j,的结点为,j(1jn),,则有如下结论成立:,(1)若,j=1,,则结点,j,为根结点,无双亲,否则,j,的双亲为,j/2,;,(2),若2,jn,,则结点,j,的左子女为2,j,否则无左子女。即满足2,jn,的结点为叶子结点;,(3)若2,j+1n,,则结点,j,的右子女为2,j+1,,否则无右子女;,(4)若结点,j,序号为奇数且不等于1,则它的左兄弟为,j-1;,(5),若结点,j,序号为偶数且不等于,n,,它的右兄弟为,j+1;,(6),结点,j,所在层数(层次)为,log,2,j,+1;,6.2.3,二叉树的存贮结构,1顺序存贮结构,将一棵二叉树按完全二叉树顺序存放到一个一维数组中,若该二叉树为非完全二叉树,则必须将相应位置空出来,使存放的结果符合完全二叉树形状。如图6-7给出了顺序存贮形式。,对于一棵二叉树,若采用顺序存贮时,当它为完全二叉树时,比较方便,若为非完全二叉树,将会浪费大量存贮存贮单元。最坏的非完全二叉树是全部只有右分支,设高度为,K,则需占用2,K,-1,个存贮单元,而实际只有,k,个元素,实际只需,k,个存储单元。因此,对于非完全二叉树,宜采用下面的链式存储结构。,2二叉链表存贮结构,(1)二叉链表表示,将一个结点分成三部分,一部分存放结点本身信息,另外两部分为指针,分别存放左、右孩子的地址。,二叉链表中一个结点可描述为:,对于图6-7所示二叉树,用二叉链表形式描述见图6-8。,对于一棵二叉树,若采用二叉链表存贮时,当二叉树为非完全二叉树时,比较方便,若为完全二叉树时,将会占用较多存贮单元(存放地址的指针)。若一棵二叉树有,n,个结点,采用二叉链表作存贮结构时,共有2,n,个指针域,其中只有,n-1,个指针指向左右孩子,其余,n+1,个指针为空,没有发挥作用,被白白浪费掉了,(当然后面介绍的线索可利用它)。,(2)二叉链表的数据类型,二叉链表的数据类型描述如下:,struct bitree,elemtype,data ;/,结点数据类型,bitree,*,lchild,*,rchild,;/,定义左、右孩子为指针型,(3)二叉链表的建立,为了后面遍历二叉树方便,先介绍建立二叉链表的算法(假设,elemtype,为,char,型)。,假设二叉链表的数据类型描述如刚才所述,为建立二叉链表,用一个一维表数组来模拟队列,存放输入的结点,但是,输入结点时,必须按完全二叉树形式,才能使结点间满足性质5,若为非完全二叉树,则必须给定一些假想结点(虚结点),使之符合完全二叉树形式。为此,我们在输入结点值时,存在的结点则输入它对应的字符,不存在的结点(虚结点),输入逗号,最后以一个特殊符号“#”作为输入的结束,表示建二叉链表已完成。建成的二叉链表可以由根指针,root,唯一确定。,算法描述如下:,#,include,typedef,char,elemtype,;,struct bitree,elemtype,data;,bitree,*,lchild,*,rchild,;,bitree,*create(),bitree,*q100;/,定义,q,数组作为队列存放二叉链表中结点,100为最大容量,bitree,*s;/,二叉链表中的结点,bitree,*root;/,二叉链表的根指针,int,front=1,rear=0;/,定义队列的头、尾指针,char,ch,;/,结点的,data,域值,root=NULL;,cin,ch,;,while(,ch,!=#)/,输入值为#号,算法结束,s=NULL;,if(,ch,!=,)/,输入数据不为逗号,表示不为虚结点,否则为虚结点,s=new,bitree,;s-data=,ch,;,s-,lchild,=NULL;s-,rchild,=NULL;,rear+;,qrear=s;/,新结点或虚结点进队,if(rear=1)root=s;,else,if(s!=NULL)&(qfront!=NULL),if(rear%2=0)qfront-,lchild,=s;/rear,为偶数,s,为双亲左孩子,else qfront-,rchild,=s;/rear,为奇数,s,为双亲右孩子,if(rear%2=1)front+;/,出队,cin,ch,;,return root;,例如,对图6-9所示的二叉树,建立的二叉链表如图6-10所示。,对图6-9(,a),所示的二叉树,要用算法建成图6-10所示的二叉树链表,从键盘输入的数据应为:,AB,C,D#,其中#为输入结束,为回车符。,6.3遍历二叉树,所谓遍历二叉树,就是遵从某种次序,访问二叉树中的所有结点,使得每个结点仅被访问一次。,这里提到的“访问”是指对结点施行某种操作,操作可以是输出结点信息,修改结点的数据值等,但要求这种访问不破坏它原来的数据结构。在本书中,我们规定访问是输出结点信息,data,,且以二叉链表作为二叉树的存贮结构。,由于二叉树是一种非线性结构,每个结点可能有一个以上的直接后继,因此,必须规定遍历的规则,并按此规则遍历二叉树,最后得到二叉树所有结点的一个线性序列。,令,L,R,D,分别代表二叉树的左子树、右子树、根结点,则遍历二叉树有6种规则:,DLR、DRL、LDR、LRD、RDL、RKD。,若规定二叉树中必须先左后右(左右顺序不能颠倒),则只有,DLR、LDR、LRD,三种遍历规则。,DLR,称为前根遍历(或前序遍历、先序遍历、先根遍历),,LDR,称为中根遍历(或中序遍历),,LRD,称为后根遍历(或后序遍历)。,6.3.1,前根遍历,所谓前根遍历,就是根结点最先遍历,其次左子树,最后右子树。,1递归遍历,前根遍历二叉树的递归遍历算法描述为:,若二叉树为空,则算法结束;否则,(1)输出根结点;,(2)前根遍历左子树;,(3)前根遍历右子树;,算法如下:,void preorder(,bitree,*root),bitree,*p;,p=root;,if(p!=NULL),cout,data,lchild,);,preorder(p-,rchild,);,2非递归遍历,利用一个一维数组作为栈,来存储二叉链表中结点,算法思想为:,从二叉树根结点开始,沿左子树一直走到末端(左孩子为空)为止,在走的过程中,访问所遇结点,并依次把所遇结点进栈,当左子树为空时,从栈顶退出某结点,并将指针指向该结点的右孩子。如此重复,直到栈为空或指针为空止。,算法如下:,void preorder1(,bitree,*root),bitree,*p,*s100;,int,top=0;/top,为栈顶指针,p=root;,while(p!=NULL)|(top0),while(p!=NULL),cout,data,lchild,;,p=stop-;p=p-,rchild,;,6.3.2,中根遍历,所谓中根遍历,就是根在中间,先左子树,然后根结点,最后右子树。,1递归遍历,中根遍历二叉树的递归遍历算法描述为:,若二叉树为空,则算法结束;否则,中根遍历左子树;,输出根结点;,中根遍历右子树。,算法如下:,void,inorder,(,biteee,*root),bitree,*p;,p=root;,if(p!=NULL),inorder,(p-,lchild,);,cout,data,rchild,);,2非递归遍历,同样利用一个一维数组作栈,来存贮二叉链表中结点,算法思想为:,从二叉树根结点开始,沿左子树一直走到末端(左孩子为空)为止,在走的过程中,把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复,直到栈空或指针为空止。,算法如下:,void inorder1(,bitree,*root),bitree,*p,*s100;/s,为一个栈,,top,为栈顶指针,int,top=0;,p=root;,while(p!=NULL)|(top0),while(p!=NULL),s+top=p;p=p-,lchild,;,p=stop-;,cout,data,rchild,;,6.3.3,后根遍历,所谓后根遍历,就是根在最后,即先左子树,然后右子树,最后根结点。,1递归遍历,后根遍历二叉树的递归遍历算法描述为:,若二叉树为空,则算法结束;否则,(1)后根遍历左子树:,(2)后根遍历历子树;,(3)访问根结点。,算法如下:,void,postorder,(,bitree,*root),bitree,*p;,p=root;,if (p!=NULL),postorder,(p-,lchild,);,postorder,(p-,rchild,);,cout,data,lchild,;,if(top0),b=s2-top;,p=s1top;,if(b=0),s1top=p;s2top+=1;/,第二次进栈标志为0,p=p-,rchild,;,else,cout,data0);,例如,可以利用上面介绍的遍历算法,写出如图6-11所示二叉树的三种遍历序列为:,先序遍历序列:,ABDGCEFH,中序遍历序列:,BGDAECFH,后序遍历序列:,GDBEHFCA,另外,在编译原理中,有用二叉 树来表示一个算术表达式的情形。在一棵二叉树中,若用操作数代表树叶,运算符代表非叶子结点,则这样的树可以代表一个算术表达式。若按前序、中序、后序对该二叉树进行遍历,则得到的遍历序列分别称为前缀表达式(或称波兰式)、中缀表达式、后缀表达式(递波兰式)。具体参见图6-12。,图6-12所对应的前缀表达式:-*,abc,。,图6-12所对应的中缀表达式:,a*b-c。,图6-12所对应的后缀表达式:,ab,*c-。,二叉树所对应的遍历序列可以通过递归算法得到,也可以通过非递归算法得到。但有时要求直接写出序列,故我们可以用图6-13所示得到图6-12的遍历序列。从二叉树的三种递归遍历算法可以知道,三种遍历算法不同之处在于访问根结点和遍历左、右子树的顺序不同,若递归算法中去掉与递归无关的语句访问根结点,则三个遍历算法完全相同。于是对于二叉树的遍历,可以看成是从根结点出发,往左子树走,若左子树为空,返回,再进入右子树,右子树访问完后,再返回根结点。这样一来每个结点都被访问三次,若将按顺序第一次访问的结点排列起来,则得到该二叉树的先序序列,第二次访问的结点排列起来,则得到该二叉树的中序序列,第三次访问的结点排列起来,则得到该二叉树的后序序列。对于图6-13中,第一次访问到的结点用表示,第二次访问到的结点用表示,第三次访问的结点用表示,按虚线顺序将所有排列,则得到先序序列为-*,abc,将所有排列起来则得到中序序列为,a*b-c,将所有排列起来则得到后序序列,ab,*c-。,6.3.4遍历算法应用举例,例6-5 由二叉树的前序序列和中序序列建立该二叉树,分析:若二叉树的任意两个结点的值都不相同,则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外,由前序序列和中序序列的定义可知,前序序列中第一个结点必为根结点,而在中序序列中,根结点刚好是左、右子树的分界点,因此,可按如下方法建立二叉树:,1.用前序序列的第一个结点作为根结点;,2.在中序序列中查找根结点的位置,并以此为界将中序序列划分为左、右两个序列(左、右子树);,3.根据左、右子树的中序序列中的结点个数,将前序序列去掉根结点后的序列划分为左、右两个序列,它们分别是左、右子树的前序序列;,4.对左、右子树的前序序列和中序序列递归地实施同样方法,直到所得左、右子树为空。,假设前序序列为,ABDGHCEFI,,中序序列为,GDHBAECIF,,则,得到的二叉树如下页所示,1。,A,为根结点,A BDGH CEFI,GDHB A ECIF,BD,GH,CE,FI,A,2.,B,为左子树的根结点,B DGH,GDH B,CE,FI,DH,G,B,A,3.,D,为左子树的左子树的根结点,4。,C,为右子树的根结点,5。,F,为右子树的右子树的根结点,C E,FI,E C IF,例6-6 按层次遍历一棵二叉树,对于一棵二叉树,若规定遍历顺序为从上到下(上层遍历完才进入下层),从左到右(同一层从左到右进行,这样的遍历称为按层次遍历:例6-5的树的层次遍历序列为:,ABCDEFGHI。,下面用一个一维数组来模拟队列,实现二叉树的层次遍历。,Void,lorder,(,bitree,*t),bitree,*q,maxsize,*p;/,maxsize,为最大容量,int,f,r;/f,r,类似于头尾指针,q1=t;f=r=1;,while(f,lchild,!=NULL),r+;qr=p-1child;/,入队,if (p-,rchild,!=NULL),r+;qr=p-,rchild,;/,入队,6.4线索二叉树,6.4.1 线索的概念,通过前面介绍的二叉树可知,遍历二叉树实际上就是将树中所有结点排成一个线性序列(即非线性结构线性化),在这样的线性序列中,很容易求得某个结点在某种遍历下的直接前驱和后继。然而,有时我们希望不进行遍历就能快速找到某个结点在某种遍历下的直接前驱和后继,这样,就应该把每个结点的直接前驱和直接后继记录下来。为了做到这一点,可以在原来的二叉链表结点中,再增加两个指针域,一个指向前驱,一个指向后继,但这样做将会浪费大量存贮单元,存贮空间的利用率相当低(一个结点中有4个指针,1个指左孩子,1个指右孩子,1个指前驱,1个指后继),而原来的左、右孩子域有许多空指针又没有利用起来。为了不浪费存存贮空间,我们利用原有的孩子指针为空时来存放直接前驱和后继,这样的指针称为“线索”,加线索的过程称为线索化,加了线索的二叉树,称为线索二叉树,对应的二叉链表称为线索二叉链表。,在线索二叉树中,由于有了线索,无需遍历二叉树就可以得到任一结点在某种遍历下的直接前驱和后继。但是,我们怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息呢?为此,在二叉链表结点中,还必须增加两个标志域,ltag,、,rtag,。,ltag,和,rtag,定义如下:,0,lchild,域指向结点的左孩子,ltag,=,1,lchild,域指向结点在某种遍历下的直 接前驱,0,rchild,域指向结点的右孩子,rtag,=,1,rchild,域指向结点在某种遍历下的直接后继,这样,二叉链表中每个结点还是有5个域,但其中只有2个指针,较原来的4个指针要方便。增加线索后的二叉链表结点结构可描述如下:,2线索的分类,另外,根据遍历的不同要求,线索二叉树可以分为:,(1)前序前驱线索二叉树(只需画出前驱),(2)前序后继线索二叉树(只需画出后继),(3)前序线索二叉树(前驱和后继都要标出),(4)中序前驱线索二叉树(只需画出前驱),(5)中序后继线索二叉树(只需画出中序后继),(6)中序线索二叉树(中序前驱和后继都要标出),(7)后序前驱线索二叉树(只需画出后序前驱),(8)后序后继线索二叉树(中需画出后序后驱),(9)后序线索二叉树(后前驱和后继都要标出),6.4.2线索的描述,1结点数据类型描述,struct Hbitree,elemtype,data;,int ltag,rtag,;/,左、右标志域,Hbitree,*,lchild,*,rchild,;,2线索的画法,在二叉树或二叉链表中,若左孩子为空,则画出它的直接前驱,右孩子为空时,则画出它的直接后继,左右孩子不为空时,不需画前驱和后继。这样就得到了线索二叉树或线索二叉链表。,前序,序列为:,ABCD,中序,序列为:,BADC,后序,序列为:,BDCA,6.4.3 线索的算法实现,在此,仅介绍中序线索二叉树的算法实现,设为,P,为当前结点,,pre,为,p,的前驱结点,算法描述如下:,void,inth,(,Hbitree,*p),/,将,P,所指二叉树中序线索化,调用该函数之前,,pre,为,Null,,而树中所有结点的,ltag,和,rtag,都为0。,if(p!=NULL),inth,(p-,lchild,);,左子树线索化,if (p-,lchild,=,NULLl,),p-,ltag,=1;,if(p-,rchild,=NULL)p-,rtag,;,if(pre!=NULL),if(pre-,rtag,=1)pre-,rchild,=p;,if(p-,ltag,=1)p-,lchild,=pre;,pre=p;,inth,(p-,rchild,);/,右子树线索化,6.4.4 线索二叉树上的运算,1线索二叉树上的查找,(1)查找指定结点在中序线索二叉树中的的直接后继,若所找结点右标志,rtag,=1,,则右孩子域指向中序后继,否则,中序后继应为遍历右子树时的第一个访问结点,即右子树中最左下的结点(参见图 6-19)。从图6-19中可知,,x,的后继为,x,k,。,(2)查找指定结点在中序线索二叉树中的的直接,前驱,若所找结点左标志,ltag,=1,,则左孩子域指向中序前驱,否则,中序前驱应为遍历左子树时的最后一个访问结点,即左子树中最右下的结点(参见图 6-20)。从图6-20中可知,,x,的前驱为,x,k,。,(3)查找指定点在前序线索二叉树中的直接后继,前序后继的查找比较方便,若无左孩子,右链为后继,否则左孩子为后继。,(4)查找指定结点在后序线索二叉树中的直接前驱,后序前驱的查找也比较方便,若左孩子为空,左链指前驱,否则,若右子树为空,左孩子指前驱,否则右孩子为前驱。,求后序后继和前序前驱都比较麻烦,在此不再作进一步介绍。,2线索二叉树上的遍历,遍历某种次序的线索二叉树,只要从该次序下的开始结点出发,反复找到结点在该次序下的后继,直到后继为空。这对于中序线索和前序线索二叉树很方便,但对于后序线索二叉树较麻烦(因求后序后继较麻烦)。故后序线索对于遍历没有什么意义。,(1)前序遍历线索二叉树算法,void preorder2(,Hbitree,*t),Hbitree,*p;,p=t;/,找到开始结点,while(p!=NULL),cout,data;,p=,preordernext,(p);/,调查函数找前序后继,(2)中序遍历线索二叉树算法,void inorder2 (,Hbitree,*t),Hbitree,*p;p=t;,if(p!=NULL),while(p-,ltag,=0)p=p-,lchild,;/,找开始结点,while(p!=NULL),cout,data;,p=,inordernext,(p);/,调用函数找中序后继,从上面算法可知,线索二叉树上的遍历较一般二叉树要方便得多。但是这种方便是以增加线索为代价的,增加线索本身要花费大量时间。所以二叉树是以二链表表示,还是以线索二叉链表示,可根据具体问题而定。,3线索二叉树的扦入和删除,线索二树上的查找、遍历都较一般二叉树方便,但线索二叉树也存在其缺点,就扦入和删除运算而言,线索二叉树比一般二叉树的时间花费大,因为除修改指针外,还要修改相应线索。,线索二叉树的扦入和删除较麻烦,因此本书不再介绍算法,.树和森林,.树的存储结构,1双亲表示,它是以一组连续的存储单元来存放树中的结点,每个结点有两个域:一个是,data,域,存放结点信息,另一个是,parent,域,用来存放双亲的位置(指针)。,该结构的具体描述见图6-21。,2孩子表示法,将一个结点所有孩子链接成一个单链表形,而树中有若干个结点,故有若干个单链表,每个单链表有一个表头结点,所有表头结点用一个数组来描述,具体描述参见图6-22,3双亲孩子表示法,将第1、2两种方法结合起来,则得到双亲孩子表示法,具体参见图6-23。,4。孩子兄弟表示法,类似于二叉链表,但第一根链指向第一个孩子,第二根链指向下一个兄弟。将图6-21(,a),的树用孩子兄弟表示法表示,见图6-24。,6.5.2 树、森林和二叉树的转换,1树转换成二叉树,可以分为三步:,(1)连线,指相邻兄弟之间连线。,(2)抹线,指抹掉双亲与除左孩子外其它孩子之间的连线。,(3)旋转,只需将树作适当的旋转。,具体实现过程见图6-25。,2森林转换成二叉树,(1)将森林中每一棵树分别转换成二叉树,这在刚才的树转换成二叉树中已经介绍过。,(2)合并,使第,n,棵树接入到第,n-1,棵的右边并成为它的右子树,第,n-1,棵二叉树接入到第,n-2,棵的右边并成为它的右子树,第2棵二叉树接入到第1棵的右边并成为它的右子树,直到最后剩下一棵二叉树为止。,3二叉树还原成树或森林,(1),右链断开,将二叉树的根结点的右链及右链的右链等全部断开,得到若干棵无右子树的二叉树。,具体操作见图6-27(,b)。,(2),二叉树还原成树,将(1)中得到的每一棵二叉树都还原成树(与树转换成二叉树的步骤刚好相反)。,具体操作步骤见图6-27(,c)。,6.5.3 树和森林的遍历,在树和森林中,一个结点可能有两棵以上的子树,所以不宜讨论它们的中序遍历,即树和森林只有先序遍历和后序遍历。,1先序遍历,(1)树的先序遍历,若树非空,则先访问根结点,然后依次先序遍历各子树。,(2)森林的先序遍历,若森林非空,则先访问森林中第一棵树的根结点,再先序遍历第一棵树各子树,接着先序遍历第二棵树、第三棵树、直到最后一棵树。,2后序遍历,(1)树的后序遍历,若树非空,则依次后序遍历各子树,最后访问根结点。,(2)森林的后序遍历,按顺序后序遍历森林中的每一棵树。,另外,请注意,树和森林的先序遍历等价于它转换成的二叉树的先序遍历,树和森林的后序遍历等价于它转换成的二叉树的中序遍历。,6.6 哈夫曼树,6.6.1,基本术语,1路径和路径长度,在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路,称为路径。通路中分支的数目称为路径长度。,若规定根结点的层数为1,则从根结点到第,L,层结点的路径长度为,L-1。,2结点的权及带权路径长度,若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。,结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。,3树的带权路径长度,树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为,wpl,=,,其中,n,为叶子结点数目,,w,i,为第,i,个叶子结点的权值,,l,i,为第,i,个叶子结点的路径长度。,6.6.2 哈夫曼树构造,1哈夫曼树的定义,在一棵二叉树中,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(,Huffman tree)。,例如,给定叶子结点的权分别为1,3,5,7,则可以得到如图6-28所示的不同二叉树。,从图6-28可知,图6-28(,b),的长度最短,图6-28(,c),为较差情形,当然读者还可以自已构造出具有不同的,wpl,情形来。,2哈夫曼树的构造,假设有,n,个权值,则构造出的哈夫曼树有,n,个叶子结点。,n,个权值分别设为,w,1,w,2,w,n,则哈夫曼树的构造规则为:,(1)将,w,1,w,2,w,n,看成是有,n,棵树的森林(每棵树仅有一个结点);,(2)在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;,(3)从森林中删除选取的两棵树,并将新树加入森林;,(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为我们所求得的哈夫曼树。,下面给出哈夫曼树的构造过程,假设给定的叶子结点的权分别为1,5,7,3,则构造哈夫曼树过程如图6-29所示。,从图6-29可知,,n,个权值构造哈夫曼树需,n-1,次合并,每次合并,森林中的树数目减1,最后森林中只剩下一棵树,即为我们求得的哈夫曼树。,6.6.3哈夫曼树的应用,1哈夫曼编码,通信中,可以采用0,1的不同排列来表示不同的字符,称为二进制编码。而哈夫曼树在数据编码中的应用,是数据的最小冗余编码问题,它是数据压缩学的基础。若每个字符出现的频率相同,则可以采用等长的二进制编码,若频率不同,则可以采用不等长的二进编码,频率较大的采用位数较少的编码,频率较小的字符采用位数较多的编码,这样可以使字符的整体编码长度最小,这就是最小冗余编码的问题。而哈夫曼编码就是一种不等长的二进制编,码,且哈夫曼树是一种最优二叉树,它的编码也是一种最优编码,在哈夫曼树中,规定往左编码为0,往右编码为1,则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。,例如,给定权1,5,7,3,得到的哈夫曼树及编码见图6-32(假定权值就代表该字符名字)。,2哈夫曼译码,在通信中,若将字符用哈夫曼编码形式发送出去,对方接收到编码后,将编码还原成字符的过程,称为哈夫曼译码。,
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:数据结构(C++描述)_树.ppt
    链接地址:https://www.zixin.com.cn/doc/13777279.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


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

    自信网络  |  ZixinNetwork