数据结构第14讲-线索树与树和森林.ppt
《数据结构第14讲-线索树与树和森林.ppt》由会员分享,可在线阅读,更多相关《数据结构第14讲-线索树与树和森林.ppt(46页珍藏版)》请在装配图网上搜索。
第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.3.1遍历二叉树6.3.2线索二叉树6.4树和森林6.6赫夫曼树及其应用,6.3.2线索二叉树,1.何谓线索二叉树?遍历结果是求得结点的一个线性序列。指向该线性序列“前驱”和“后继”的指针,称“线索”;包含“线索”的存储结构,称为“线索链表”;与其相应的二叉树,称为“线索二叉树”;对二叉树以某种次序遍历,使其变为线索二叉树的过程,称为“线索化”。,2.线索链表中结点的结构,在二叉链表的结点结构中增加两个标志域,并规定:,其中:LTag=,0lchild域指示结点的左孩子1lchild域指示结点的前驱,RTag=,0rchild域指示结点的右孩子1rchild域指示结点的后继,二叉树二叉线索存储表示,typedefenumLink,ThreadPointerThr;/Link=0:指针,Thread=1:线索typedefstructBiThrNodeTElemTypedata;StructBiThrNode*lchild,*rchild;/左右孩子指针PointerThrLTag,RTag;/左右标志BiThrNode,*BiThrTree;,3.线索二叉树图例,线索二叉树及其存储结构(a)中序线索二叉树(b)中序线索链表,如何在线索树中找结点的后继?,结合中序线索树若其右标志为“1”,右链是线索,右链直接指示了结点的后继;若其右标志为“0”,右链是指针,其后继为右子树中最左下的结点。,如何在线索树中找结点的前驱?,结合中序线索树若其左标志为“1”,左链为线索,直接指示其前驱;若其左标志为“0”,左子树中最右下的结点为其前驱。,线索链表的中序遍历算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)/T指向头结点,头结点的左链lchild指向根结点,中序遍历/二叉线索树T的非递归算法,对每个数据元素调用函数Visit。p=T-lchild;/p指向根结点while(p!=T)/空树或遍历结束时,p=Twhile(p-LTag=Link)p=p-lchild;if(!Visit(p-data)returnERROR;/访问其左子树为空的结点while(p-RTag=Thread/IOTraver_T,4.如何建立线索化链表?,由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索,而前驱或后继的信息只有在遍历时才能得到,因此线索化的过程即为在遍历的过程中修改空指针的过程。,对二叉链表p进行中序线索化的递归算法(带头结点),StatusInOrderThreading(BiThrTree调用不带头结点的中序线索化的递归算法;3.最后一个结点线索化(指向头结点),voidInThreading(BiThrTreep)if(p)InThreading(p-lchild);/左子树线索化if(!p-lchild)p-lchild=pre;p-ltag=Thread;/前驱线索if(!pre-rchild)pre-rchild=p;pre-rtag=Thread;/后继线索pre=p;/保持pre指向p的前驱InThreading(p-rchild);/右子树线索化InThreading,对二叉链表p进行中序线索化的递归算法(不带头结点),StatusInOrderThreading(BiThrTree,StatusInOrderThreading(BiThrTree/空树,Thrt回指自身,Thrt,Link,Thread,1,elseThrt-lchild=T;/头结点的lchild指向二叉链表根pre=Thrt;/pre指向前驱结点InThreading(T);/中序线索化二叉链表Tpre-rchild=Thrt;pre-rtag=Thread;/最后一个结点线索化Thrt-rchild=pre;returnOK;,Thrt,pre,输出:BCAED,1,0,1,1,1,1,1,0,0,0,0,pre,P=null,T,A,B,D,E,C,F,G,例:对下图的树按先序、后序、中序线索化,第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.4.3树和森林的遍历6.6赫夫曼树及其应用,6.4.1树的存储结构,三种常用的链表结构:双亲表示法孩子表示法孩子兄弟表示法,1.双亲表示法即以一组连续空间存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。,树的双亲表存储表示#defineMAX_TREE_SIZE100typedefstructPTNode/结点结构Elemdata;intparent;/双亲位置域PTNode;typedefstruct/树结构PTNodenodesMAX_TREE_SIZE;intr,n;/根结点的位置和结点个数PTree;,分析:这种存储结构利用每个结点(除根结点)只有唯一双亲的性质,Parent(T,x)操作可在常量时间内实现。反复调用Parent操作,直到遇见无双亲的结点时,便找到了树的根。但在这种表示方式中,求结点的孩子时需遍历整个结构。,2.孩子表示法由于树中每个结点可能有多棵子树,则考虑用多重链表,即结点有多个指针域,其中每个指针指向一棵子树的根结点,此时链表中的结点可以有如下两种结点格式:,采用第一种格式多重链表中的结点是同构的,其中dx为树的度。由于树中很多结点的度小于dx,所以链表中有很多空链域,造成空间浪费。,采用第二种格式多重链表中的结点是不同构的,其中dy为结点的度,drgee域的值同dy,此时可以节省存储空间,但操作不方便。,有没有既能节省空间又操作方便的办法呢?,另一种方式把每个结点的孩子结点排列起来,看成是一个线性表,且以单链表作存储结构,则n个结点有n个孩子链表(叶子的孩子链表为空)。而n个头指针又组成一个线性表,为便于查找,采用顺序存储结构。,树的孩子链表存储表示typedefstructCTNode/孩子结点intchild;structCTNode*next;*ChildPtr;typedefstruct/双亲结点结构Elemdata;ChildPtrfirstchild;/孩子链的头指针CTBox;typedefstruct/树结构:CTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根结点的位置CTree;,分析:与双亲表示法相反,孩子表示法便于涉及孩子的操作实现,却不适用于Parent(T,x)操作。可根据某种需要,将二者结合起来,即带双亲的孩子链表。,3.孩子兄弟表示法或称二叉树表示法,或称二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。,3.孩子兄弟表示法例:,树的二叉链表(孩子-兄弟)存储表示typedefstructCSNodeElemdata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;,分析:这种存储结构便于实现各种树的操作。首先易于实现找结点孩子等的操作。如果为每个结点增设一个(parent)域,则同样能方便地实现Parent(T,x)操作。,6.4.2森林和二叉树的转换,1.树和二叉树的对应关系由于二叉树和树都可用二叉链表作为存储结构,则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。,树转换为二叉树方法:,1)对每个孩子进行从左到右的排序;2)在兄弟之间加一条连线;3)对每个结点,除了左孩子外,去除其与其余孩子之间的联系;4)以根结点为轴心,将整个树顺时针转45。,2.森林和二叉树的对应关系从树的二叉链表表示的定义可知,任何一棵和树对应的二叉树,其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟,则同样可导出森林和二叉树的对应关系。,已知条件:森林和二叉树的对应关系设森林F=(T1,T2,Tn);T1=(root,t11,t12,t1m);二叉树B=(LBT,Node(root),RBT);由森林转换成二叉树的转换规则为:若F=,则B=;否则,由Root(T1)对应得到Node(root);由(t11,t12,t1m)对应得到LBT;由(T2,T3,Tn)对应得到RBT。由二叉树转换为森林的转换规则为:若B=,则F=;否则,由Node(root)对应得到Root(T1);由LBT对应得到(t11,t12,,t1m);T1除根以外所构成的森林由RBT对应得到(T2,T3,Tn);除T1之外的森林,6.4.3树和森林的遍历,1.树的遍历:有三条搜索路径先根(序)遍历:若树不空,则先访问根结点,然后依次先根遍历各棵子树。后根(序)遍历:若树不空,则先依次后根遍历各棵子树,然后访问根结点。按层次遍历:若树不空,则自上而下自左至右访问树中每个结点。,例对树进行先根遍历,获得的先根序列是:对树进行后根遍历,获得的后根序列是:,ABEFCDGHI,EFBCGHIDA,2.森林的遍历,先序遍历(对森林中的每一棵树进行先根遍历)1)若森林不空,访问森林中第一棵树的根结点;2)先序遍历森林中第一棵树的子树森林;3)先序遍历森林中(除第一棵树外)其余树构成的森林。后序遍历(对森林中的每一棵树进行后根遍历)1)若森林不空,后序遍历森林中第一棵树的子树森林;2)访问森林中第一棵树的根结点;3)后序遍历森林中(除第一棵树外)其余树构成的森林。,例:对森林进行先序遍历,获得的先序序列是:对森林进行后序遍历,获得的后序序列是:,BEFCDGHI,EFBCGHID,总结:1.二叉树的线索化2.树的表示及其遍历操作;3.建立森林与二叉树的对应关系。由于在树和森林中,一个结点的孩子的个数不定,它们在计算机中的表示以及在各种操作计算机中的算法实现均不易实现,因此将树和森林表示为二叉树,并将对树和森林的操作转化为对二叉树的操作是通常采用的方法。,1)假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。画出该二叉树。2)线索二叉树是一种()结构。A、逻辑B、物理C、线性3)试找出分别满足下面条件的所有二叉树。A、先序序列和中序序列相同;B、后序序列和中序序列相同;C、先序序列和后序序列相同;,树和二叉树的习题,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 14 线索 森林
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文