二叉树的遍历 课件

《二叉树的遍历 课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.4二叉树的遍历7.4.1二叉树遍历的定义所谓二叉树的遍历，是指按一定的顺序对二叉树中的每个结点均访问一次，且仅访问一次。按照根结点访问位置的不同，通常把二叉树的遍历分为六种：TLR（根左右）,TRL（根右左）LTR（左根右）,RTL（右根左）LRT（左右根）,RLT（右左根）其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为前序遍历、中序遍历和后序遍历。（1）二叉树的前序遍历首先访问根结点；

2、然后按照前序遍历的顺序访问根结点的左子树；再按照前序遍历的顺序访问根结点的右子树。（2）二叉树的中序遍历首先按照中序遍历的顺序访问根结点的左子树；然后访问根结点；最后按照中序遍历的顺序访问根结点的右子树。（3）二叉树的后序遍历首先按照后序遍历的顺序访问根结点的左子树；然后按照后序遍历的顺序访问根结点的右子树；最后访问根结点。abdfegc前序遍历：abdefgc中序遍历:debgfac后序遍历:edgfbca练习！！！！！！！！GHA图5-15DEFBC前序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBE

3、HFCA练习！！！！！！！！下面我们再给出一种遍历二叉树的方法（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。DGBAECHFGHDEFBCA图5-167.4.2二叉树遍历的递归实现由于二叉树的遍历是递归定义的，因此采用递归方式实现二叉树遍历的算法十分方便，只要按照各种遍历规定的次序，访问根结点时就输出根结点的值，访问左子树和右子树时进行递归调用即可。1、前序遍历二叉树的

4、递归算法voidpreorder(bintreet){if(t){printf("%c",t->data);preorder(t->lchild);preorder(t->rchild);}}遍历二叉树递归算法2、中序遍历二叉树的递归算法voidinorder(bintreet){if(t){inorder(t->lchild);printf(“%c”,t->data);inorder(t->rchild);}}3、后序遍历二叉树的递归算法voidpostorder(bintreet){if(t){postorder(t->lchild)

5、;postorder(t->rchild);printf("%c",t->data);}}4、二叉树的创建算法利用二叉树前序遍历的结果可以非常方便地生成给定的二叉树，具体做法是：将第一个输入的结点作为二叉树的根结点，后继输入的结点序列是二叉树左子树前序遍历的结果，由它们生成二叉树的左子树；再接下来输入的结点序列为二叉树右子树前序遍历的结果，应该由它们生成二叉树的右子树；而由二叉树左子树前序遍历的结果生成二叉树的左子树和由二叉树右子树前序遍历的结果生成二叉树的右子树的过程均与由整棵二叉树的前序遍历结果生成该二叉树的过程完全相同，只是所处理的

6、对象范围不同，于是完全可以使用递归方式加以实现。voidcreatebintree(bintree*t){charch;if((ch=getchar())=='')*t=NULL;else{*t=(bintnode*)malloc(sizeof(bintnode));/*生成二叉树的根结点*/(*t)->data=ch;createbintree(&(*t)->lchild);/*递归实现左子树的建立*/createbintree(&(*t)->rchild);/*递归实现右子树的建立*/}}7.4.3二叉树遍历的非递归实现第5章介

7、绍了由递归程序转换成非递归程序的两种方法：简单递归程序的转换和复杂递归程序的转换；二叉树的遍历问题应该属于后者，即在采用非递归方式实现二叉树遍历时，必须使用一个堆栈记录回溯点，以便将来进行回溯。以下为一个顺序栈的定义及其部分操作的实现。typedefstructstack/*栈结构定义*/{bintreedata[100];inttag[100];//为栈中每个元素设置的标记，用于后序遍历inttop;//栈顶指针,指向栈顶元素,这和2章中top有区别}seqstack;voidpush(seqstack*s,bintreet)/*进栈*

8、/{s->data[++s->top]=t;}bintreepop(seqstack*s)/*出栈*/{if(s->top!=-1){s->top--;return(s->data[s->t