二叉树遍历(递归-非递归转换)-课件

——遍历二叉树制作人：计科系孙玉霞数据结构12/24/20221数据结构——二叉树的遍历 ——遍历二叉树制作人：计科系孙玉霞数据结构12/16/20

遍历二叉树二叉树的先序遍历二叉树的中序遍历二叉树的后序遍历6.3遍历二叉树本次课主要内容2遍历二叉树6.3遍历二叉树本次课主要内容2遍历二叉树方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL返回目录3遍历二叉树DLRLDR、LRD、DLR返回目录3ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC二叉树的先序遍历4ADBCDLR算法实现：进入非递归算法递归算法先序遍历过程演示5算法实现：进入递归算法先序遍历5voidpreorder(BiTreet){if(t!=NULL){printf("%d\t",t->data);preorder(t->lchild);preorder(t->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDCTTTTBack6voidpreorder(BiTreet)主程序Pre(非递归算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)7非递归算法ABCDEFGpiP->A(1)ABCDEFGpipABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)8pABCDEFGiP->A访问：CB(5)ABCDEFGiABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)9ABCDEFGiP->AP->DP->G访问：CBEP=ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)ABCDEFGi访问：CBEGDFAp=NULL(15)返回目录10ABCDEFGiP->A访问：CBEGDFp=NU二叉树的中序遍历一、二叉树中序遍历的定义：首先按照中序遍历的顺序访问根结点的左子树；然后访问根结点；最后按照中序遍历的顺序访问根结点的右子树。中序遍历的结果：HtHABCDEJIFGKLDKJLBEIAFCG11二叉树的中序遍历一、二叉树中序遍历的定义：中序遍历的结果二、二叉树中序遍历的递归实现#defineNULL0Typedefstructnode{chardata;structnode*lchild,*rchild;}*BiTree;Voidinorder(BiTreet){if(t!=NULL){ inorder(t–>lchild); printf(“%c”,t–>data) inorder(t–>rchild); }}12二、二叉树中序遍历的递归实现#defineNULL012三、二叉树中序遍历的非递归实现tHABCDEJIFGKL需保存的结点：ABDHtttt=^t输出：Ht=^tJKDttt=^t=^tKtJtLt=^t=^LttBt剩下的遍历过程由同学们自行完成！13三、二叉树中序遍历的非递归实现tHABCDEJIFGKL需保在二叉树中序遍历过程中：（2）在遍历过程中要做的工作始终分成两部分：当前正在访问的子树（被指针t指向）栈中等待访问的子树当t所指向的子树访问完成后，若栈非空，则取出栈顶元素，访问其根结点，然后再进入其右子树访问（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（3）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。14在二叉树中序遍历过程中：（2）在遍历过程中要做的工作始终分成二叉树中序遍历的非递归实现算法：typedefstructstack{/*栈结构定义*/BiTreedata[100];inttop;}sqstack;

voidpush(sqstack*s,BiTreet)/*进栈*/

{s.data[s++]=t;

}

BiTreepop(sqstack*s)/*出栈*/

{

if(s!=0)

return(s.data[--s]);

else

returnNULL;

}15二叉树中序遍历的非递归实现算法：typedefstruvoidinorder1(BiTreet)/*非递归实现二叉树中序遍历*/

{sqstacks;

s=0;

while((t!=NULL)||(s!=0))

{while(t!=NULL)

{push(&s,t);t=t->lchild;}

if(s!=0)

{t=pop(&s);

printf("%c",t->data);

t=t->rchild;

}

}

}返回目录16voidinorder1(BiTreet)/*非二叉树的后序遍历一、二叉树后序遍历的定义：首先按照后序遍历的顺序访问根结点的左子树；然后按照后序遍历的顺序访问根结点的右子树。最后访问根结点；后序遍历的结果：HKLJDIEBFGCAtHABCDEJIFGKL17二叉树的后序遍历一、二叉树后序遍历的定义：后序遍历的结果二、二叉树后序遍历的递归实现

voidpostorder(BiTreet)

{

if(t!=NULL) {

postorder(t->lchild);

postorder(t->rchild);

printf("%c",t->data);

}

}18二、二叉树后序遍历的递归实现

18三、二叉树后序遍历的非递归实现tHABCDEJIFGKL需保存的结点：ABDHtttt=^t输出：Ht=^tKKttt=^t=^tJtt=^Ltt’剩下的遍历过程由同学们自行完成！t’J’tt’Lt=^t’ttDt’过程演示19三、二叉树后序遍历的非递归实现tHABCDEJIFGKL需保在二叉树后序遍历过程中：（2）在遍历过程中要做的工作始终分成两部分：

当前正在访问的子树（被指针t指向）栈中等待访问的子树（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（3）当t为空或t所指向的子树访问完成后，若栈非空，则考虑两种情况：

若栈顶元素的右子树尚未访问，则访问其右子树，此时栈顶元素不能出栈；若栈顶元素的右子树已被访问，则访问该栈顶元素，并将其出栈；20在二叉树后序遍历过程中：（2）在遍历过程中要做的工作始终分成因此为了区分栈顶元素的右子树是否已被访问，可为其设置一标志tag.

tag=0，表示该栈顶元素的右子树尚未访问，该栈顶元素不能出栈，而应该进入其右子树进行访问；

tag=1，表示该栈顶元素的右子树已被访问，可将该栈顶元素出栈，并输出其值；

显然，当一个元素刚进入栈时，其tag值应该为0，而当进入栈顶元素的右子树访问时，应该将其tag值改为1。（4）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。请同学们仔细分析对照后序遍历和中序遍历的区别！二叉树后序遍历和中序遍历的主要区别在于对栈顶元素的处理，即以上第（3）点。21因此为了区分栈顶元素的右子树是否已被访问，可为其设置一标志t二叉树后序遍历的非递归实现算法：voidpostorder1(BiTreet)

{sqstacks;

s=0;

while((t!=NULL)||(s!=0))

{while(t!=NULL)

{s.data[s]=t; s.tag[s]=0; s++; t=t->lchild;}

typedefstructstack/*栈结构定义*/

{BiTreedata[100];

inttag[100];/*为栈中每个元素设置的标记*/

inttop;/*栈顶指针*/

}sqstack;22二叉树后序遍历的非递归实现算法：voidpostorderwhile((s>0)&&(s.tag[s]==1))

{t=s.data[s];

printf("%c",t->data); s--;

}

if(s>0)

{t=s.data[s];

s.tag[s]=1;

t=t->rchild;

}

elset=NULL;

}

}

23while((s>0)&&(s.ta总结:“遍历”是二叉树各种操作的基础。由上讨论得知：遍历二叉树是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。这实质上是对一个非线性结构进行线性化。返回目录24总结:返回目录24-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef练习题1：25-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历

Thankyou拯畏怖汾关炉烹霉躲渠早膘岸缅兰辆坐蔬光膊列板哮瞥疹傻俘源拯割宜跟三叉神经痛-治疗三叉神经痛-治疗拯畏怖汾关炉烹霉躲渠早膘岸缅兰辆坐蔬光膊列板哮瞥疹 ——遍历二叉树制作人：计科系孙玉霞数据结构12/24/202227数据结构——二叉树的遍历 ——遍历二叉树制作人：计科系孙玉霞数据结构12/16/20

遍历二叉树二叉树的先序遍历二叉树的中序遍历二叉树的后序遍历6.3遍历二叉树本次课主要内容28遍历二叉树6.3遍历二叉树本次课主要内容2遍历二叉树方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL返回目录29遍历二叉树DLRLDR、LRD、DLR返回目录3ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC二叉树的先序遍历30ADBCDLR算法实现：进入非递归算法递归算法先序遍历过程演示31算法实现：进入递归算法先序遍历5voidpreorder(BiTreet){if(t!=NULL){printf("%d\t",t->data);preorder(t->lchild);preorder(t->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDCTTTTBack32voidpreorder(BiTreet)主程序Pre(非递归算法ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B访问：C(4)33非递归算法ABCDEFGpiP->A(1)ABCDEFGpipABCDEFGiP->A访问：CB(5)ABCDEFGiP->AP->D访问：CBp(6)ABCDEFGiP->AP->DP->E访问：CBp(7)ABCDEFGiP->AP->D访问：CBEp(8)34pABCDEFGiP->A访问：CB(5)ABCDEFGiABCDEFGiP->AP->DP->G访问：CBEP=NULL(9)ABCDEFGiP->A访问：CBEGDp(11)ABCDEFGiP->AP->F访问：CBEGDp(12)ABCDEFGiP->AP->D访问：CBEGp(10)35ABCDEFGiP->AP->DP->G访问：CBEP=ABCDEFGiP->A访问：CBEGDFp=NULL(13)ABCDEFGi访问：CBEGDFAp(14)ABCDEFGi访问：CBEGDFAp=NULL(15)返回目录36ABCDEFGiP->A访问：CBEGDFp=NU二叉树的中序遍历一、二叉树中序遍历的定义：首先按照中序遍历的顺序访问根结点的左子树；然后访问根结点；最后按照中序遍历的顺序访问根结点的右子树。中序遍历的结果：HtHABCDEJIFGKLDKJLBEIAFCG37二叉树的中序遍历一、二叉树中序遍历的定义：中序遍历的结果二、二叉树中序遍历的递归实现#defineNULL0Typedefstructnode{chardata;structnode*lchild,*rchild;}*BiTree;Voidinorder(BiTreet){if(t!=NULL){ inorder(t–>lchild); printf(“%c”,t–>data) inorder(t–>rchild); }}38二、二叉树中序遍历的递归实现#defineNULL012三、二叉树中序遍历的非递归实现tHABCDEJIFGKL需保存的结点：ABDHtttt=^t输出：Ht=^tJKDttt=^t=^tKtJtLt=^t=^LttBt剩下的遍历过程由同学们自行完成！39三、二叉树中序遍历的非递归实现tHABCDEJIFGKL需保在二叉树中序遍历过程中：（2）在遍历过程中要做的工作始终分成两部分：当前正在访问的子树（被指针t指向）栈中等待访问的子树当t所指向的子树访问完成后，若栈非空，则取出栈顶元素，访问其根结点，然后再进入其右子树访问（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（3）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。40在二叉树中序遍历过程中：（2）在遍历过程中要做的工作始终分成二叉树中序遍历的非递归实现算法：typedefstructstack{/*栈结构定义*/BiTreedata[100];inttop;}sqstack;

voidpush(sqstack*s,BiTreet)/*进栈*/

{s.data[s++]=t;

}

BiTreepop(sqstack*s)/*出栈*/

{

if(s!=0)

return(s.data[--s]);

else

returnNULL;

}41二叉树中序遍历的非递归实现算法：typedefstruvoidinorder1(BiTreet)/*非递归实现二叉树中序遍历*/

{sqstacks;

s=0;

while((t!=NULL)||(s!=0))

{while(t!=NULL)

{push(&s,t);t=t->lchild;}

if(s!=0)

{t=pop(&s);

printf("%c",t->data);

t=t->rchild;

}

}

}返回目录42voidinorder1(BiTreet)/*非二叉树的后序遍历一、二叉树后序遍历的定义：首先按照后序遍历的顺序访问根结点的左子树；然后按照后序遍历的顺序访问根结点的右子树。最后访问根结点；后序遍历的结果：HKLJDIEBFGCAtHABCDEJIFGKL43二叉树的后序遍历一、二叉树后序遍历的定义：后序遍历的结果二、二叉树后序遍历的递归实现

voidpostorder(BiTreet)

{

if(t!=NULL) {

postorder(t->lchild);

postorder(t->rchild);

printf("%c",t->data);

}

}44二、二叉树后序遍历的递归实现

18三、二叉树后序遍历的非递归实现tHABCDEJIFGKL需保存的结点：ABDHtttt=^t输出：Ht=^tKKttt=^t=^tJtt=^Ltt’剩下的遍历过程由同学们自行完成！t’J’tt’Lt=^t’ttDt’过程演示45三、二叉树后序遍历的非递归实现tHABCDEJIFGKL需保在二叉树后序遍历过程中：（2）在遍历过程中要做的工作始终分成两部分：

当前正在访问的子树（被指针t指向）栈中等待访问的子树（1）必须使用栈记录尚未及时得到访问的子树的根和右子树（实际操作时只需记住子树的根即可）（3）当t为空或t所指向的子树访问完成后，若栈非空，则考虑两种情况：

若栈顶元素的右子树尚未访问，则访问其右子树，此时栈顶元素不能出栈；若栈顶元素的右子树已被访问，则访问该栈顶元素，并将其出栈；46在二叉树后序遍历过程中：（2）在遍历过程中要做的工作始终分成因此为了区分栈顶元素的右子树是否已被访问，可为其设置一标志tag.

tag=0，表示该栈顶元素的右子树尚未访问，该栈顶元素不能出栈，而应该进入其右子树进行访问；

tag=1，表示该栈顶元素的右子树已被访问，可将该栈顶元素出栈，并输出其值；

显然，当一个元素刚进入栈时，其tag值应该为0，而当进入栈顶元素的右子树访问时，应该将其tag值改为1。（4）只有t所指向的子树访问完成且栈为空时，整个遍历过程才能结束。请同学们仔细分析对照后序遍历和中序遍历的区别！二叉树后序遍历和中序遍历的主要区别在于对栈顶元素的处理，即以上第（3）点。47因此为了区分栈顶元素的右子树是否已被访问