《数据结构》-第六章 树和二叉树

第六章树和二叉树633INTIS_DESCENDANT_CINTU,INTV/在孩子存储结构上判断U是否V的子孙,是则返回1,否则返回0IFUVRETURN1ELSEIFLVIFIS_DESCENDANTU,LVRETURN1IFRVIFIS_DESCENDANTU,RVRETURN1/这是个递归算法RETURN0/IS_DESCENDANT_C634INTIS_DESCENDANT_PINTU,INTV/在双亲存储结构上判断U是否V的子孙,是则返回1,否则返回0FORPUPVPTPIFPVRETURN1ELSERETURN0/IS_DESCENDANT_P635这一题根本不需要写什么算法,见书后注释两个整数的值是相等的636INTBITREE_SIMBITREEB1,BITREEB2/判断两棵树是否相似的递归算法IFB1ELSEIFB1ELSERETURN0/BITREE_SIM637VOIDPREORDER_NONRECURSIVEBITREET/先序遍历二叉树的非递归算法INITSTACKSPUSHS,T/根指针进栈WHILESTACKEMPTYSWHILEGETTOPS,PPUSHS,PLCHILD/向左走到尽头POPS,PIFSTACKEMPTYSPOPS,PPUSHS,PRCHILD/向右一步/WHILE/PREORDER_NONRECURSIVE638TYPEDEFSTRUCTBTNODEPTRENUM0,1,2MARKPMTYPE/有MARK域的结点指针类型VOIDPOSTORDER_STACKBITREET/后续遍历二叉树的非递归算法,用栈PMTYPEAINITSTACKS/S的元素为PMTYPE类型PUSHS,T,0/根结点入栈WHILESTACKEMPTYSPOPS,ASWITCHAMARKCASE0PUSHS,APTR,1/修改MARK域IFAPTRLCHILDPUSHS,APTRLCHILD,0/访问左子树BREAKCASE1PUSHS,APTR,2/修改MARK域IFAPTRRCHILDPUSHS,APTRRCHILD,0/访问右子树BREAKCASE2VISITAPTR/访问结点,返回/WHILE/POSTORDER_STACK分析为了区分两次过栈的不同处理方式,在堆栈中增加一个MARK域,MARK0表示刚刚访问此结点,MARK1表示左子树处理结束返回,MARK2表示右子树处理结束返回每次根据栈顶元素的MARK域值决定做何种动作639TYPEDEFSTRUCTINTDATAEBTNODELCHILDEBTNODERCHILDEBTNODEPARENTENUM0,1,2MARKEBTNODE,EBITREE/有MARK域和双亲指针域的二叉树结点类型VOIDPOSTORDER_NONRECURSIVEEBITREET/后序遍历二叉树的非递归算法,不用栈PTWHILEPSWITCHPMARKCASE0PMARK1IFPLCHILDPPLCHILD/访问左子树BREAKCASE1PMARK2IFPRCHILDPPRCHILD/访问右子树BREAKCASE2VISITPPMARK0/恢复MARK值PPPARENT/返回双亲结点/POSTORDER_NONRECURSIVE分析本题思路与上一题完全相同,只不过结点的MARK值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将MARK域恢复为0,以备下一次遍历640TYPEDEFSTRUCTINTDATAPBTNODELCHILDPBTNODERCHILDPBTNODEPARENTPBTNODE,PBITREE/有双亲指针域的二叉树结点类型VOIDINORDER_NONRECURSIVEPBITREET/不设栈非递归遍历有双亲指针的二叉树PTWHILEPLCHILDPPLCHILD/向左走到尽头WHILEPVISITPIFPRCHILD/寻找中序后继当有右子树时PPRCHILDWHILEPLCHILDPPLCHILD/后继就是在右子树中向左走到尽头ELSEIFPPARENTLCHILDPPPPARENT/当自己是双亲的左孩子时后继就是双亲ELSEPPPARENTWHILEPPARENTPPPARENT/当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中的祖先/WHILE/INORDER_NONRECURSIVE641INTC,K/这里把K和计数器C作为全局变量处理VOIDGET_PRESEQBITREET/求先序序列为K的结点的值IFTC/每访问一个子树的根都会使前序序号计数器加1IFCKPRINTF“VALUEISDN“,TDATAEXIT1ELSEGET_PRESEQTLCHILD/在左子树中查找GET_PRESEQTRCHILD/在右子树中查找/IF/GET_PRESEQMAINSCANF“D“,C0/在主函数中调用前,要给计数器赋初值0GET_PRESEQT,K/MAIN642INTLEAFCOUNT_BITREEBITREET/求二叉树中叶子结点的数目IFTRETURN0/空树没有叶子ELSEIFTLCHILD/叶子结点ELSERETURNLEAF_COUNTTLCHILDLEAF_COUNTTRCHILD/左子树的叶子数加上右子树的叶子数/LEAFCOUNT_BITREE643VOIDBITREE_REVOLUTEBITREET/交换所有结点的左右子树TLCHILDTRCHILD/交换左右子树IFTLCHILDBITREE_REVOLUTETLCHILDIFTRCHILDBITREE_REVOLUTETRCHILD/左右子树再分别交换各自的左右子树/BITREE_REVOLUTE644INTGET_SUB_DEPTHBITREET,INTX/求二叉树中以值为X的结点为根的子树深度IFTDATAXPRINTF“DN“,GET_DEPTHT/找到了值为X的结点,求其深度EXIT1ELSEIFTLCHILDGET_SUB_DEPTHTLCHILD,XIFTRCHILDGET_SUB_DEPTHTRCHILD,X/在左右子树中继续寻找/GET_SUB_DEPTHINTGET_DEPTHBITREET/求子树深度的递归算法IFTRETURN0ELSEMGET_DEPTHTLCHILDNGET_DEPTHTRCHILDRETURNMNMN1/GET_DEPTH645VOIDDEL_SUB_XBITREET,INTX/删除所有以元素X为根的子树IFTDATAXDEL_SUBT/删除该子树ELSEIFTLCHILDDEL_SUB_XTLCHILD,XIFTRCHILDDEL_SUB_XTRCHILD,X/在左右子树中继续查找/ELSE/DEL_SUB_XVOIDDEL_SUBBITREET/删除子树TIFTLCHILDDEL_SUBTLCHILDIFTRCHILDDEL_SUBTRCHILDFREET/DEL_SUB646VOIDBITREE_COPY_NONRECURSIVEBITREET,BITREEINITSTACKS2PUSHS1,T/根指针进栈UBTNODEMALLOCSIZEOFBTNODEUDATATDATAQUPUSHS2,UWHILESTACKEMPTYSWHILEGETTOPS1,PQQLCHILDQDATAPDATAPUSHS1,PLCHILDPUSHS2,Q/向左走到尽头POPS1,PPOPS2,QIFSTACKEMPTYS1POPS1,PPOPS2,QQRCHILDBTNODEMALLOCSIZEOFBTNODEQQRCHILDQDATAPDATAPUSHS1,PRCHILD/向右一步PUSHS2,Q/WHILE/BITREE_COPY_NONRECURSIVE分析本题的算法系从637改写而来647VOIDLAYERORDERBITREET/层序遍历二叉树INITQUEUEQ/建立工作队列ENQUEUEQ,TWHILEQUEUEEMPTYQDEQUEUEQ,PVISITPIFPLCHILDENQUEUEQ,PLCHILDIFPRCHILDENQUEUEQ,PRCHILD/LAYERORDER648INTFOUNDFALSEBITREEFIND_NEAR_ANCIENTBITREET,BITREEP,BITREEQ/求二叉树T中结点P和Q的最近共同祖先BITREEPATHP100,PATHQ100/设立两个辅助数组暂存从根到P,Q的路径FINDPATHT,P,PATHP,0FOUNDFALSEFINDPATHT,Q,PATHQ,0/求从根到P,Q的路径放在PATHP和PATHQ中FORI0PATHPIPATHQII/查找两条路径上最后一个相同结点RETURNPATHPI/FIND_NEAR_ANCIENTVOIDFINDPATHBITREET,BITREEP,BITREEPATH,INTI/求从T到P路径的递归算法IFTPFOUNDTRUERETURN/找到PATHIT/当前结点存入路径IFTLCHILDFINDPATHTLCHILD,P,PATH,I1/在左子树中继续寻找IFTRCHILD/在右子树中继续寻找IFFOUNDPATHINULL/回溯/FINDPATH649INTISFULL_BITREEBITREET/判断二叉树是否完全二叉树,是则返回1,否则返回0INITQUEUEQFLAG0ENQUEUEQ,T/建立工作队列WHILEQUEUEEMPTYQDEQUEUEQ,PIFPFLAG1ELSEIFFLAGRETURN0ELSEENQUEUEQ,PLCHILDENQUEUEQ,PRCHILD/不管孩子是否为空,都入队列/WHILERETURN1/ISFULL_BITREE分析该问题可以通过层序遍历的方法来解决与647相比,作了一个修改,不管当前结点是否有左右孩子,都入队列这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列反之,则序列中会含有空指针650STATUSCREATEBITREE_TRIPLETBITREETBTNODEMALLOCSIZEOFBTNODEPTPDATAGETCHARGETCHAR/滤去多余字符INITQUEUEQENQUEUEQ,TWHILEPARENTGETCHARIFQUEUEEMPTYQRETURNERROR/未按层序输入PQUEUEHEADQQBTNODEMALLOCSIZEOFBTNODEIFSIDELPLCHILDQELSEIFSIDERPRCHILDQELSERETURNERROR/格式不正确QDATACHILDENQUEUEQ,QRETURNOK/CREATEBITREE_TRIPLET651STATUSPRINT_EXPRESSIONBITREET/按标准形式输出以二叉树存储的表达式IFTDATA是字母PRINTF“C“,TDATAELSEIFTDATA是操作符IFTLCHILD|TRCHILDRETURNERROR/格式错误IFTLCHILDDATA是操作符IFPRINT_EXPRESSIONTLCHILDRETURNERRORPRINTF“/注意在什么情况下要加括号ELSEIFPRINT_EXPRESSIONTLCHILDRETURNERRORIFTRCHILDDATA是操作符IFPRINT_EXPRESSIONTRCHILDRETURNERRORPRINTF“ELSEIFPRINT_EXPRESSIONTRCHILDRETURNERRORELSERETURNERROR/非法字符RETURNOK/PRINT_EXPRESSION652TYPEDEFSTRUCTBTNODENODEINTLAYERBTNRECORD/包含结点所在层次的记录类型INTFANMAOBITREET/求一棵二叉树的“繁茂度“INTCOUNTD/COUNT数组存放每一层的结点数INITQUEUEQ/Q的元素为BTNRECORD类型ENQUEUEQ,T,0WHILEQUEUEEMPTYQDEQUEUEQ,RCOUNTRLAYERIFRNODELCHILDENQUEUEQ,RNODELCHILD,RLAYER1IFRNODERCHILDENQUEUEQ,RNODERCHILD,RLAYER1/利用层序遍历来统计各层的结点数HRLAYER/最后一个队列元素所在层就是树的高度FORMAXNCOUNT0,I1COUNTIIIFCOUNTIMAXNMAXNCOUNTI/求层最大结点数RETURNHMAXN/FANMAO分析如果不允许使用辅助数组,就必须在遍历的同时求出层最大结点数,形式上会复杂一些,你能写出来吗653INTMAXHSTATUSPRINTPATH_MAXDEPTHS1BITREET/求深度等于树高度减一的最靠左的结点BITREEPATHDMAXHGET_DEPTHT/GET_DEPTH函数见644IFMAXHDATAEXIT/打印输出路径ELSEIFTLCHILDFIND_HTLCHILD,H1IFTRCHILDFIND_HTRCHILD,H1PATHHNULL/回溯/FIND_H654STATUSCREATEBITREE_SQLISTBITREE/该数组储存与SA中各结点对应的树指针IFSALASTTNULL/空树RETURNPTR1BTNODEMALLOCSIZEOFBTNODEPTR1DATASAELEM1/建立树根TPTR1FORI2IDATASAELEMIJI/2/找到结点I的双亲JIFIJ2PTRJRCHILDPTRI/I是J的右孩子ELSEPTRJLCHILDPTRI/I是J的左孩子RETURNOK/CREATEBITREE_SQLIST655INTDESCNUMBITREET/求树结点T的子孙总数填入DESCNUM域中,并返回该数IFTRETURN1ELSEDDESCNUMTLCHILDDESCNUMTRCHILD2/计算公式TDESCNUMDRETURND/DESCNUM分析该算法时间复杂度为ON,N为树结点总数注意为了能用一个统一的公式计算子孙数目,所以当T为空指针时,要返回1而不是0656BTNODEPREORDER_NEXTBTNODEP/在先序后继线索二叉树中查找结点P的先序后继,并返回指针IFPLCHILDRETURNPLCHILDELSERETURNPRCHILD/PREORDER_NEXT分析总觉得不会这么简单是不是哪儿理解错了657BITREEPOSTORDER_NEXTBITREEP/在后序后继线索二叉树中查找结点P的后序后继,并返回指针IFPRTAGRETURNPRCHILD/P有后继线索ELSEIFPPARENTRETURNNULL/P是根结点ELSEIFPPPARENTRCHILDRETURNPPARENT/P是右孩子ELSEIFPPPARENTLCHILD/P是左孩子且双亲没有右孩子ELSE/P是左孩子且双亲有右孩子QPPARENTRCHILDWHILEQLTAG|QRTAGIFQLTAGQQLCHILDELSEQQRCHILD/从P的双亲的右孩子向下走到底RETURNQ/ELSE/POSTORDER_NEXT658STATUSINSERT_BITHRTREEBITHRTREE/无法插入IFPLTAG/X作为P的左子树SPLCHILD/S为P的前驱PLTAGLINKPLCHILDXQXWHILEQLCHILDQQLCHILDQLCHILDS/找到子树中的最左结点,并修改其前驱指向SQXWHILEQRCHILDQQRCHILDQRCHILDP/找到子树中的最右结点,并修改其前驱指向PELSE/X作为P的右子树SPRCHILD/S为P的后继PRTAGLINKPRCHILDXQXWHILEQRCHILDQQRCHILDQRCHILDS/找到子树中的最右结点,并修改其前驱指向SQXWHILEQLCHILDQQLCHILDQLCHILDP/找到子树中的最左结点,并修改其前驱指向PRETURNOK/INSERT_BITHRTREE659VOIDPRINT_CSTREECSTREET/输出孩子兄弟链表表示的树T的各边FORCHILDTFIRSTCHILDCHILDCHILDCHILDNEXTSIBPRINTF“C,C,“,TDATA,CHILDDATAPRINT_CSTREECHILD/PRINT_CSTREE660INTLEAFCOUNT_CSTREECSTREET/求孩子兄弟链表表示的树T的叶子数目IFTFIRSTCHILDRETURN1/叶子结点ELSECOUNT0FORCHILDTFIRSTCHILDCHILDCHILDCHILDNEXTSIBCOUNTLEAFCOUNT_CSTREECHILDRETURNCOUNT/各子树的叶子数之和/LEAFCOUNT_CSTREE661INTGETDEGREE_CSTREECSTREET/求孩子兄弟链表表示的树T的度IFTFIRSTCHILDRETURN0/空树ELSEDEGREE0FORPTFIRSTCHILDPPPNEXTSIBDEGREE/本结点的度FORPTFIRSTCHILDPPPNEXTSIBDGETDEGREE_CSTREEPIFDDEGREEDEGREED/孩子结点的度的最大值RETURNDEGREE/ELSE/GETDEGREE_CSTREE662INTGETDEPTH_CSTREECSTREET/求孩子兄弟链表表示的树T的深度IFTRETURN0/空树ELSEFORMAXD0,PTFIRSTCHILDPPPNEXTSIBIFDGETDEPTH_CSTREEPMAXDMAXDD/子树的最大深度RETURNMAXD1/GETDEPTH_CSTREE663INTGETDEPTH_CTREECTREEA/求孩子链表表示的树A的深度RETURNSUBDEPTHAR/GETDEPTH_CTREEINTSUBDEPTHINTT/求子树T的深度IFANODESTFIRSTCHILDRETURN1FORSD1,PANODESTFIRSTCHILDPPPNEXTIFDSUBDEPTHPCHILDSDSDDRETURNSD1/SUBDEPTH664INTGETDEPTH_PTREEPTREET/求双亲表表示的树T的深度MAXDEP0FORI0I0JTNODESJPARENTDEP/求每一个结点的深度IFDEPMAXDEPMAXDEPDEPRETURNMAXDEP/GETDEPTH_PTREE665CHARPRED,IND/假设前序序列和中序序列已经分别储存在数组PRE和IN中BITREEBUILD_SUBINTPRE_START,INTPRE_END,INTIN_START,INTIN_END/由子树的前序和中序序列建立其二叉链表SROOTBTNODEMALLOCSIZEOFBTNODE/建根SROOTDATAPREPRE_STARTFORIIN_STARTINISROOTDATAI/在中序序列中查找子树根LEFTLENIIN_STARTRIGHTLENIN_ENDI/计算左右子树的大小IFLEFTLENLROOTBUILD_SUBPRE_START1,PRE_STARTLEFTLEN,IN_START,IN_STARTLEFTLEN1SROOTLCHILDLROOT/建左子树,注意参数表的计算IFRIGHTLENRROOTBUILD_SUBPRE_ENDRIGHTLEN1,PRE_END,IN_ENDRIGHTLEN1,IN_ENDSROOTRCHILDRROOT/建右子树,注意参数表的计算RETURNSROOT/返回子树根/BUILD_SUBMAINBUILD_SUB1,N,1,N/初始调用参数,N为树结点总数分析本算法利用了这样一个性质,即一棵子树在前序和中序序列中所占的位置总是连续的因此,就可以用起始下标和终止下标来确定一棵子树PRE_START,PRE_END,IN_START和IN_END分别指示子树在前序子序列里的起始下标,终止下标,和在中序子序列里的起始和终止下标666TYPEDEFSTRUCTCSNODEPTRCSNODELASTCHILDNODEMSG/结点的指针和其最后一个孩子的指针STATUSBULID_CSTREE_PTREEPTREET/由树T的双亲表构造其孩子兄弟链表NODEMSGTREEDFORI0IDATATNODEIDATA/建结点IFTNODESIPARENT0/不是树根JTNODESIPARENT/本算法要求双亲表必须是按层序存储IFTREEJLASTCHILD/双亲当前还没有孩子TREEJPTRFIRSTCHILDTREEIPTR/成为双亲的第一个孩子ELSE/双亲已经有了孩子TREEJLASTCHILDNEXTSIBTREEIPTR/成为双亲最后一个孩子的下一个兄弟TREEJLASTCHILDTREEIPTR/成为双亲的最后一个孩子/IF/FOR/BULID_CSTREE_PTREE667TYPEDEFSTRUCTCHARDATACSNODEPTRCSNODELASTCHILDNODEINFO/结点数据,结点指针和最后一个孩子的指针STATUSCREATECSTREE_DUPLETCSTREEN1K0IFGETCHARRETURNERROR/未按格式输入IFCGETCHARTNULL/空树TREE0PTRCSNODEMALLOCSIZEOFCSNODETREE0DATACTREE0PTRDATACWHILEPGETCHARTREENDATACTREENPTRDATACFORK0TREEKDATAPK/查找当前边的双亲结点IFTREEKDATAPRETURNERROR/未找到未按层序输入RTREEKPTRIFRFIRSTCHILDRFIRSTCHILDTREENPTRELSETREEKLASTCHILDNEXTSIBTREENPTRTREEKLASTCHILDTREENPTR/这一段含义同上一题N/WHILERETURNOK/CREATECSTREE_DUPLET668STATUSCREATECSTREE_DEGREECHARNODE,INTDEGREE/由结点的层序序列和各结点的度构造树的孩子兄弟链表CSNODEPTRD/树结点指针的辅助存储PTR0CSNODEMALLOCSIZEOFCSNODEI0K1/I为当前结点序号,K为当前孩子的序号WHILENODEIPTRIDATANODEIDDEGREEIIFDPTRKCSNODEMALLOCSIZEOFCSNODE/K为当前孩子的序号PTRIFIRSTCHILDPTRK/建立I与第一个孩子K之间的联系FORJ2JNEXTSIBPTRK/当结点的度大于1时,为其孩子建立兄弟链表/FOR/IFI/WHILE/CREATECSTREE_DEGREE669VOIDPRINT_BITREEBITREET,INTI/按树状打印输出二叉树的元素,I表示结点所在层次,初次调用时I0IFTRCHILDPRINT_BITREETRCHILD,I1FORJ1JDATA/打印T元素,换行IFTLCHILDPRINT_BITREETRCHILD,I1/PRINT_BITREE分析该递归算法实际上是带层次信息的中序遍历,只不过按照题目要求,顺序为先右后左670STATUSCREATEBITREE_GLISTBITREEIFCTNULL/空子树ELSETCSNODEMALLOCSIZEOFCSNODETDATACIFGETCHARRETURNERRORIFCREATEBITREE_GLISTPLRETURNERRORTLCHILDPLIFGETCHAR,RETURNERRORIFCREATEBITREE_GLISTPRRETURNERRORTRCHILDPRIFGETCHARRETURNERROR/这些语句是为了保证输入符合AB,C的格式RETURNOK/CREATEBITREE_GLIST671VOIDPRINT_CSTREECSTREET,INTI/按凹入表形式打印输出树的元素,I表示结点所在层次,初次调用时I0FORJ1JDATA/打印元素,换行FORPTFIRSTCHILDPPPNEXTSIBPRINT_CSTREEP,I1/打印子树/PRINT_CSTREE672VOIDPRINT_CTREEINTE,INTI/按凹入表形式打印输出树的元素,I表示结点所在层次FORJ1JNEXTPRINT_CSTREEPCHILD,I1/打印子树/PRINT_CSTREEMAINPRINT_CTREETR,0/初次调用时I0/MAIN673CHARC/全局变量,指示当前字符STATUSCREATECSTREE_GLISTCSTREETCSNODEMALLOCSIZEO