武汉理工大学-信息工程学院-数据结构-ppt-课件ch06-3-树和二叉树3-线索二叉树和森林

第6章树和二叉树3数据结构讲义-线索二叉树和森林信息工程学院魏洪涛Email:[e-mail]6.3.2线索二叉树定义：–前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~–线索：指向前驱或后继结点的指针称为~–线索二叉树：加上线索的二叉链表表示的二叉树叫~–线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~实现：–在有n个结点的二叉链表中必定有n+1个空链域–在线索二叉树的结点中增加两个标志域ltag:若ltag=0,lchild域指向左孩子；若ltar=1,lchild域指向其前驱rtag:若rtag=0,rchild域指向右孩子；若rtag=1,rchild域指向其后继ABCDEABDCET先序序列：ABCDE先序线索二叉树00001111^11typedefstructnode{intdata;intltag,rtag;structnode*lchild,*rchild;}JD;lchildltagdatartagrchildABCDEABDCET中序序列：BCAED中序线索二叉树00001111^11^ABCDEABDCET后序序列：CBEDA后序线索二叉树0000111111^算法–遍历中序线索二叉树在中序线索二叉树中找结点后继的方法：（1）若rtag=1,则rchild域直接指向其后继（2）若rtag=0,则结点的后继应是其右子树的左链尾（ltag=1)的结点在中序线索二叉树中找结点前驱的方法：（1）若ltag=1,则lchild域直接指向其前驱（2）若ltag=0,则结点的前驱应是其左子树的右链尾（rtag=1)的结点ABCDE0A01B00D11C11E1T中序序列：BCAED带头结点的中序线索二叉树6.4树和森林树的存储结构双亲表示法–实现：定义结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置–特点：找双亲容易，找孩子难typedefstructnode{datatypedata;intparent;}JD;JDt[M];abcdefhgiacdefghib012235551096012345789dataparent0号单元不用或存结点个数如何找孩子结点孩子表示法–多重链表：每个结点有多个指针域，分别指向其子树的根结点同构：结点的指针个数相等，为树的度D结点不同构：结点指针个数不等，为该结点的度ddatachild1child2……….childDdatadegreechild1child2……….childd–孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表孩子结点：typedefstructnode{intchild;//该结点在表头数组中下标structnode*next;//指向下一孩子结点}JD;表头结点：typedefstructtnode{datatypedata;//数据域structnode*fc;//指向第一个孩子结点}TD;TDt[M];//t[0]不用abcdefhgi6012345789acdefghibdatafc23^45^^978^6^^^^^如何找双亲结点–带双亲的孩子链表612345789acdefghibdatafc23459786^^^^^^^^^012235551parentabcdefhgi孩子兄弟表示法（二叉树表示法）–实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点–特点操作容易破坏了树的层次typedefstructnode{datatypedata;structnode*fch,*nsib;}JD;abcdefhgiabcdefghi^^^^^^^^^^树与二叉树转换ACBED树ABCDE二叉树A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^对应将树转换成二叉树–加线：在兄弟之间加一连线–抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系–旋转：以树的根结点为轴心，将整树顺时针转45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空将二叉树转换成树–加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来–抹线：抹掉原二叉树中双亲与右孩子之间的连线–调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI森林转换成二叉树–将各棵树分别转换成二叉树–将每棵树的根结点用线相连–以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉树转换成森林–抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树–还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ树和森林的遍历树的遍历–遍历——按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列–常用方法先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO讨论：若采用“先转换，后遍历”方式，结果是否一样？abdec先序遍历：后序遍历：中序遍历：decbaabdecabcdebdcea1.树的先序遍历二法相同；2.树的后序遍历相当于对应二叉树的中序遍历；3.树没有中序遍历，因为子树无左右之分。结论：先序遍历若森林为空，返回；访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历若森林为空，返回；中序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林。森林的遍历ABCDEFGHJI讨论：若采用“先转换，后遍历”方式，结果是否相同？例如：ABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG结论：森林的先序和中序遍历在两种方式下的结果相同。结论：当以二叉链表做树的存储结构时，树的先根序列和后根序列可借用二叉树的先序遍历和后序遍历的算法实现之；对于森林也一样。作业1.画出先序线索左图的二叉树的存储结构。2.把右图所示的树转化成二叉树(画出图形)。ABCDEFG