叉树的遍历和应用.ppt

1,二叉树的遍历和应用,数据结构与算法,2,预备知识递归,3,什么是递归？,递归是极强大的问题解决技术。当一个函数用它自己来定义时就是递归。递归将一个复杂问题分解为一些更小的问题。,4,举例：查词典,顺序查找：可以从词典第一页开始，按顺序查找每个单词，直到找到。递归解决方案：分而治之的策略；把问题划分成小问题，直到到达基例。,查找词典,查找词典的前半部分,查找词典的后半部分,5,递归解决方案的一般形式,怎样按同类型的更小的问题来定义问题各个递归调用怎么减小问题规模哪个问题实例可用做基例随着问题规模的减小，最终能否到达基例,6,举例1：n的阶乘,publicstaticintfact(intn)/computethefactorialofanonnegativeinteger/precondition:nmustbegreaterthanorequalto0/postcondition:returnsthefactorialofn/-if(n=0)return1;Elsereturnn*fact(n-1);/endif/endfact,7,举例2：逆置字符串,减小规模：去掉最后一个字符writeBackward(s)if(thestringsisempty)donothingthisisthebasecaseElseWritethelastcharacterofswriteBackward(sminusitslastcharacter)/endif/end,减小规模：去掉第一个字符writeBackward2(s)if(thestringsisempty)donothingthisisthebasecaseElsewriteBackward2(sminusitsfirstcharacter)Writethefirstcharacterofs/endif/end,8,举例3：Hanoi塔,solveTowers(count,source,destination,spare)if(countis1)Moveadiskdirectlyfromsourcetodestination;ElsesloveTowers(count-1,source,spare,destination)sloveTowers(1,source,destination,spare)sloveTowers(count-1,spare,destination,source)/endif/end,9,举例4：兔子繁殖(递归法),publicstaticintrabbit(intn)if(n2,10,举例4：兔子繁殖(迭代法),publicstaticintiterativeRabbit(intn)/iterativesolutiontotherabbitproblem/initializebasecases:intprevious=1;/rabbit(1)intcurrent=1;/rabbit(2)intnext=1;/resultwhennis1or2/computernextrabbitvalueswhenn=3for(inti=3;ileft();preorder(subroot-right();,遍历二叉树的递归实现,23,课后思考,思考遍历算法的非递归算法思想描述。由先序、中序和后序中任意两个序列能够唯一确定一颗二叉树？,24,遍历算法的应用举例,1、统计二叉树中叶子结点的个数(先序遍历),2、求二叉树的深度(后序遍历),3、复制二叉树(后序遍历),4、建立二叉树的存储结构,25,1、统计二叉树中叶子结点的个数,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。,26,voidCountLeaf(BiTreeT,int/if/CountLeaf,27,TraversalExample,/Returnthenumberofnodesinthetreetemplateintcount(BinNode*subroot)if(subroot=NULL)return0;/Nothingtocountif(subroot.isleaf()return1;/thenodeisleafreturncount(subroot-left()+count(subroot-right();,28,2、求二叉树的深度,算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,29,求二叉树的深度的伪代码设计。,请利用上课讲述的方法设计出该问题的详细算法，多写几个,课后复习,30,二叉树的存储,31,存于顺序存储结构,32,以字符串的形式根左子树右子树定义一棵二叉树,例如:,A,B,C,D,以空白字符“”表示,A(B(,C(,),D(,),空树,只含一个根结点的二叉树,A,以字符串“A”表示,以下列字符串表示,33,StatusCreateBiTree(BiTree/CreateBiTree,34,ABCD,A,B,C,D,上页算法执行过程举例如下：,A,T,B,C,D,35,仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，,由二叉树的先序和中序序列建树,如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,36,abcdefg,cbdaegf,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,37,voidCrtBT(BiTreeelse/CrtBT,38,T=(BiTNode*)malloc(sizeof(BiTNode);T-data=preps;if(k=is)T-Lchild=NULL;elseCrtBT(T-Lchild,pre,ino,ps+1,is,k-is);if(k=is+n-1)T-Rchild=NULL;elseCrtBT(T-Rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1);,39,二叉树的线索化,40,何谓线索二叉树？,遍历二叉树的结果是，求得结点的一个线性序列。,A,B,C,D,E,F,G,H,K,例如:,先序序列:ABCDEFGHK,中序序列:BDCAHGKFE,后序序列:DCBHKGFEA,41,指向该线性序列中的“前驱”和“后继”的指针，称作“线索”,与其相应的二叉树，称作“线索二叉树”,包含“线索”的存储结构，称作“线索链表”,ABCDEFGHK,D,C,B,E,42,在二叉链表的结点中增加两个标志域，并作如下规定：,data,LTag,RTag,LChild,RChild,LTag=,RTag=,0LChild域指示结点的左孩子,1LChild域指示结点的前驱,0RChild域指示结点的右孩子,1RChild域指示结点的后继,43,在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。,如何建立线索链表？,44,45,voidInThreading(BiThrTreep)if(p)/对以p为根的非空二叉树进行线索化InThreading(p-lchild);/左子树线索化if(!p-lchild)/建前驱线索p-LTag=Thread;p-lchild=pre;if(!pre-rchild)/建后继线索pre-RTag=Thread;pre-rchild=p;pre=p;/保持pre指向p的前驱InThreading(p-rchild);/右子树线索化/if/InThreading,46,StatusInOrderThreading(BiThrTree/InOrderThreading,47,if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;/处理最后一个结点pre-RTag=Thread;Thrt-rchild=pre;,48,父指针表示和等价类问题,49,父指针表示法,50,等价类问题,父指针表示法可以有效的解答下述问题:给出两个结点，它们是否在同一棵树中?/ReturnTRUEifnodesindifferenttreesboolGentree:differ(inta,intb)introot1=FIND(a);/Findrootforaintroot2=FIND(b);/Findrootforbreturnroot1!=root2;/Compareroots,51,Union/Find,voidGentree:UNION(inta,intb)introot1=FIND(a);/Findrootforaintroot2=FIND(b);/Findrootforbif(root1!=root2)arrayroot2=root1;intGentree:FIND(intcurr)constwhile(arraycurr!=ROOT)curr=arraycurr;returncurr;/Atroot,52,等价类处理的例子(1),53,等价类处理的例子(2),54,重量权衡合并规则,需要降低树的高度.Weightedun