二叉树遍历讲课教案

6.3二叉树的遍历一、问题的提出二、先左后右的遍历算法三、算法的递归描述四、中序遍历算法的非递归描述五、遍历算法的应用举例顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。一、问题的提出“访问”的含义可以很广，如：输出结点的信息等。“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：typedefstructBiTNode{//结点结构TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:二叉树C语言的类型描述如下:若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：三、算法的递归描述StatusPreorder(BiTreeT,void(*visit)(TElemType&e)){//先序遍历二叉树if(T){visit(T-data);//访问结点Preorder(T-lchild,visit);//遍历左子树Preorder(T-rchild,visit);//遍历右子树}}说明访问函数的示例和preOrder函数调用的方法算法6.1所示.同理可以实现中序遍历二叉树和后序遍历二叉树.3种遍历思想一致,不同之处在于访问根结点的时机先序:访问左子树之前访问根中序:访问右子树之前访问根后序:访问右子树之后访问根ABCDFEHI四、用堆栈实现二叉树中序遍历ABCDFEHIABCDFEHIAABABDDBABA^DA^BACCA^C^AFFEFEIIEF^EFI^FE^FHH^H^用堆栈实现二叉树中序遍历的规律将根结点设置为待入栈结点p如果p不为空,则p入栈,将p的左孩子设置为待入栈结点如果p为空,则栈顶元素出栈,访问栈顶元素,然后将栈顶元素的右孩子设置为待入栈结点直到P为空且栈为空结束算法见书上6.3五、遍历算法的应用举例2、建立二叉树的存储结构1、求二叉树的深度(后序遍历)1、求二叉树的深度(后序遍历)算法基本思想:从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。首先分析二叉树的深度和它的左、右子树深度之间的关系。intDepth(BiTreeT){//返回二叉树的深度if(!T)depthval=0;else{depthLeft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);}returndepthval;}2、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法以字符串的形式根左子树右子树定义一棵二叉树例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空树只含一个根结点的二叉树A以字符串“A”表示以下列字符串表示ABCDABCD基本的构造过程举例如下：ATBCD^^^^^StatusCreateBiTree(BiTree&T){scanf(&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T-data=ch;//生成根结点CreateBiTree(T-lchild);//构造左子树CreateBiTree(T-rchild);//构造右子树}returnOK;}//CreateBiTree仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树如果同时已知二叉树的中序序列“cbdaegf”，则会如何？二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列思考:已知中序遍历：BDCEAFHG已知后序遍历：DECBHGFA（BDCE）BFGHCDEA作业:1.写出中序遍历二叉树的递归算法2.写出计算二叉树叶结点个数的递归算法叶结点满足的条件3.给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树，并写出该二叉树的前序遍历序列和中序遍历序列。6.5线索二叉树何谓线索二叉树？线索链表的遍历算法如何建立线索链表？一、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序序列:ABCDEFGHK——如何记录树中每个结点在遍历序列中直接前驱和直接后继因为：用二叉链表法存储包含n个结点的二叉树，结点的指针区域中会有n+1个空指针。可以利用这些空指针来指示前驱或后继指向该线性序列中的“前驱”和“后继”的指针，称作“线索”与其相应的二叉树，称作“线索二叉树”包含“线索”的存储结构，称作“线索链表”ABCDEFGHK^D^C^^BE^对线索链表中结点的约定：在二叉链表的结点中增加两个标志域(bit)，ltag(左)和rtag(右)并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且设置ltag的值为“0”；否则，Lchild域的指针指向其“前驱”，且设置ltag的值为“1”。若该结点的右子树不空，则rchild域的指针指向其右子树，且设置rtag的值为“0”；否则，rchild域的指针指向其“后继”，且设置rtag的值为“1”。如此定义的二叉树的存储结构称作“线索链表”。增加了前驱和后继等线索有什么好处？——能方便找出当前结点的前驱和后继，不用堆栈（递归）也能遍历整个树。ABCGEIDHFroot悬空？NULL悬空？NULL对该二叉树中序遍历的结果为:H,D,I,B,E,A,F,C,G所以添加线索应当按如下路径进行：为避免悬空态，应增设一个头结点例:画出以下二叉树对应的中序线索二叉树。线索二叉树的生成——线索化过程线索化过程就是在遍历过程中修改空指针的过程00A00C00B11E11F11G00D11I11H注：此图中序遍历结果为:H,D,I,B,E,A,F,C,G0root1对应的中序线索二叉树存储结构如图所示：typedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;//左右指针PointerTagLTag,RTag;//左右标志}BiThrNode,*BiThrTree;线索链表的类型描述：typedefenum{Link,Thread}PointerTag;//Link==0:指针，Thread==1:线索二、线索链表的遍历算法:由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。例如:对中序线索化链表的遍历算法※中序遍历的第一个结点？※在中序线索化链表中结点的后继？根结点的左子树上处于“最左下”（没有左子树）的结点。若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(TElemTypee)){p=T-lchild;//p指向根结点while(p!=T){//空树或遍历结束时，p==Twhile(p-LTag==Link)p=p-lchild;//第一个结点while(p-RTag==Thread&&p-rchild!=T){p=p-rchild;Visit(p-data);//访问后继结点}p=p-rchild;//p进至其右子树根}}//InOrderTraverse_Thr(1)对二叉树中序遍历的同时建立线索.(2)访问结点:在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息.(3)如何记录前驱和后继结点:遍历过程中，附设指针pre,并始终保持指针pre指向当前访问的、指针p所指结点的前驱。三、如何建立中序线索链表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}//InThreadingStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//构建中序线索链表if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;//添加头结点returnOK;}//InOrderThreading……if(!T)Thrt-lchild=Thrt;else{Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;//处理最后一个结点pre-RTag=Thread;Thrt-rchild=pre;}小结7.4二叉树遍历7.4.1二叉树遍历7.4.2二叉链存储结构下二叉树遍历的实现7.5线索二叉树1.有关线索二叉树的几个术语2.线索二叉树的生成——线索化作业:给定如图所示二叉树T，请画出与其对应的中序线索二叉树。2825405560330854后续内容6.4树与二叉树的转换6.6哈夫曼树