1、1,2023/6/12,数据结构二叉树的遍历,遍历二叉树,制作人:计科系孙玉霞,数据结构,2,遍历二叉树二叉树的先序遍历二叉树的中序遍历二叉树的后序遍历,6.3 遍历二叉树,本次课主要内容,2,3,遍历二叉树方法先序遍历:先访问根结点,然后分别先序遍历左子树、右子树中序遍历:先中序遍历左子树,然后访问根结点,最后中序遍历右子树后序遍历:先后序遍历左、右子树,然后访问根结点按层次遍历:从上到下、从左到右访问各结点,返回目录,3,4,D L R,先序遍历序列:A B D C,二叉树的先序遍历,4,5,算法实现:,进入非递归算法,先序遍历过程演示,5,6,void preorder(BiTree t
2、)if(t!=NULL)printf(%dt,t-data);preorder(t-lchild);preorder(t-rchild);,返回,返回,返回,返回,A,C,B,D,返回,先序序列:A B D C,Back,6,7,非递归算法,7,8,8,9,9,10,返回目录,10,11,二叉树的中序遍历,一、二叉树中序遍历的定义:首先按照中序遍历的顺序访问根结点的左子树;然后访问根结点;最后按照中序遍历的顺序访问根结点的右子树。,中序遍历的结果:,H,D,K,J,L,B,E,I,A,F,C,G,11,12,二、二叉树中序遍历的递归实现,#define NULL 0Typedef struct
3、 node char data;struct node*lchild,*rchild;*BiTree;Void inorder(BiTree t)if(t!=NULL)inorder(tlchild);printf(“%c”,tdata)inorder(trchild);,12,13,三、二叉树中序遍历的非递归实现,B,D,H,t=,输出:H,t=,J,K,D,t=,t=,K,J,L,t=,t=,L,B,剩下的遍历过程由同学们自行完成!,13,14,在二叉树中序遍历过程中:,(2)在遍历过程中要做的工作始终分成两部分:当前正在访问的子树(被指针t指向)栈中等待访问的子树 当t所指向的子树访问完
4、成后,若栈非空,则取出栈顶元素,访问其根结点,然后再进入其右子树访问,(1)必须使用栈记录尚未及时得到访问的子树的根和右子树(实际操作时只需记住子树的根即可),(3)只有t所指向的子树访问完成且栈为空时,整个遍历过程才能结束。,14,15,二叉树中序遍历的非递归实现算法:,typedef struct stack/*栈结构定义*/BiTree data100;int top;sqstack;void push(sqstack*s,BiTree t)/*进栈*/s.datas.top+=t;BiTree pop(sqstack*s)/*出栈*/if(s.top!=0)return(s.data-
5、s.top);else return NULL;,15,16,void inorder1(BiTree t)/*非递归实现二叉树中序遍历*/sqstack s;s.top=0;while(t!=NULL)|(s.top!=0)while(t!=NULL)push(,返回目录,16,17,二叉树的后序遍历,一、二叉树后序遍历的定义:首先按照后序遍历的顺序访问根结点的左子树;然后按照后序遍历的顺序访问根结点的右子树。最后访问根结点;,后序遍历的结果:,HKLJDIEBFGCA,17,18,二、二叉树后序遍历的递归实现 void postorder(BiTree t)if(t!=NULL)posto
6、rder(t-lchild);postorder(t-rchild);printf(%c,t-data);,18,19,三、二叉树后序遍历的非递归实现,B,D,H,t=,输出:H,t=,K,K,t=,t=,J,t=,L,剩下的遍历过程由同学们自行完成!,J,L,t=,D,过程演示,19,20,在二叉树后序遍历过程中:,(2)在遍历过程中要做的工作始终分成两部分:当前正在访问的子树(被指针t指向)栈中等待访问的子树,(1)必须使用栈记录尚未及时得到访问的子树的根和右子树(实际操作时只需记住子树的根即可),(3)当t 为空或t 所指向的子树访问完成后,若栈非空,则考虑两种情况:若栈顶元素的右子树尚
7、未访问,则访问其右子树,此 时栈顶元素不能出栈;若栈顶元素的右子树已被访问,则访问该栈顶元素,并将其出栈;,20,21,因此为了区分栈顶元素的右子树是否已被访问,可为其设置一标志tag.tag=0,表示该栈顶元素的右子树尚未访问,该栈顶元素不能出栈,而应该进入其右子树进行访问;tag=1,表示该栈顶元素的右子树已被访问,可将该栈顶元素出栈,并输出其值;显然,当一个元素刚进入栈时,其tag值应该为0,而当进入栈顶元素的右子树访问时,应该将其tag值改为1。(4)只有t所指向的子树访问完成且栈为空时,整个遍历过程才能结束。,请同学们仔细分析对照后序遍历和中序遍历的区别!,二叉树后序遍历和中序遍历的
8、主要区别在于对栈顶元素的处理,即以上第(3)点。,21,22,二叉树后序遍历的非递归实现算法:,void postorder1(BiTree t)sqstack s;s.top=0;while(t!=NULL)|(s.top!=0)while(t!=NULL)s.datas.top=t;s.tags.top=0;s.top+;t=t-lchild;,typedef struct stack/*栈结构定义*/BiTree data100;int tag100;/*为栈中每个元素设置的标记*/int top;/*栈顶指针*/sqstack;,22,23,while(s.top0),23,24,总结:“遍历”是二叉树各种操作的基础。由上讨论得知:遍历二叉树是以一定规则将二叉树中的结点排列成一个线性序列,得到二叉树中结点的先序序列或中序序列或后序序列。这实质上是对一个非线性结构进行线性化。,返回目录,24,25,先序遍历:,中序遍历:,后序遍历:,层次遍历:,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,练习题1:,25,
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2