《数据结构—二叉树》由会员分享,可在线阅读,更多相关《数据结构—二叉树(38页珍藏版)》请在金锄头文库上搜索。
1、 7.4 二叉树的遍历 7.4.1 二叉树遍历的定义 所谓二叉树的遍历,是指按一定的顺序对二叉 树中的每个结点均访问一次,且仅访问一次。 按照根结点访问位置的不同,通常把二叉树的 遍历分为六种:TLR(根左右), TRL(根右左) LTR(左根右), RTL(右根左)LRT(左右根), RLT(右左根)n其中,TRL、RTL和RLT三种顺序在左右子树之间均 是先右子树后左子树,这与人们先左后右的习惯不 同,因此,往往不予采用。余下的三种顺序TLR、 LTR和LRT根据根访问的位置不同分别被称为前序遍 历、中序遍历和后序遍历。 (1)二叉树的前序遍历首先访问根结点;然后按照前序遍历的顺序访问根结
2、点的左子树;再按照前序遍历的顺序访问根结点的右子树。(2)二叉树的中序遍历 首先按照中序遍历的顺序访问根结点的左子树; 然后访问根结点; 最后按照中序遍历的顺序访问根结点的右子树。(3)二叉树的后序遍历 首先按照后序遍历的顺序访问根结点的左子树; 然后按照后序遍历的顺序访问根结点的右子树; 最后访问根结点。abdfegc前序遍历:前序遍历:abdefgcabdefgc中序遍历中序遍历: : debgfacdebgfac后序遍历后序遍历: : edgfbcaedgfbca练习!G HA图 5-15D E FB C前序序列:ABDGCEFH 中序序列:DGBAECHF 后序序列:GDBEHFCA练
3、习!n下面我们再给出一种遍历二叉树的方法n (1)对一棵二叉树中序遍历时,若我们将二叉树严格地按左子树的所有结点位于根结点的左侧,右子树的所有结点位于根右侧的形式绘制,就可以对每个结点做一条垂线,映射到下面的水平线上,由此得到的顺序就是该二叉树的中序遍历序列。D G B A E C H F G HD E FB CA图 5-167.4.2 二叉树遍历的递归实现 由于二叉树的遍历是递归定义的,因此采用递 归方式实现二叉树遍历的算法十分方便,只要按 照各种遍历规定的次序,访问根结点时就输出根结点 的值,访问左子树和右子树时进行递归调用即可。1 、前序遍历二叉树的递归算法 void preorder(
4、bintree t) if (t) printf(“%c“,t-data); preorder(t-lchild);preorder(t-rchild); 遍历二叉树递归算法n2 、中序遍历二叉树的递归算法void inorder(bintree t) if (t) inorder(t-lchild);printf(“%c”,t-data);inorder(t-rchild); 3 、后序遍历二叉树的递归算法void postorder(bintree t) if (t) postorder(t-lchild);postorder(t-rchild);printf(“%c“,t-data);
5、4 、二叉树的创建算法 n 利用二叉树前序遍历的结果可以非常方便地生成给定的 二叉树,具体做法是:将第一个输入的结点作为二叉树的 根结点,后继输入的结点序列是二叉树左子树前序遍历的 结果,由它们生成二叉树的左子树;再接下来输入的结点 序列为二叉树右子树前序遍历的结果,应该由它们生成二 叉树的右子树;而由二叉树左子树前序遍历的结果生成二 叉树的左子树和由二叉树右子树前序遍历的结果生成二叉 树的右子树的过程均与由整棵二叉树的前序遍历结果生成 该二叉树的过程完全相同,只是所处理的对象范围不同, 于是完全可以使用递归方式加以实现。nvoid createbintree(bintree *t) char
6、 ch;if (ch=getchar()= ) *t=NULL;else *t=(bintnode *)malloc(sizeof(bintnode); /*生成二叉树的根结点*/(*t)-data=ch;createbintree( /*递归实现左子树的建立*/createbintree( /*递归实现右子树的建立*/ 7.4.3 二叉树遍历的非递归实现 n第5章介绍了由递归程序转换成非递归程序的两种方法 :简单递归程序的转换和复杂递归程序的转换;n二叉树的遍历问题应该属于后者,即在采用非递归方式 实现二叉树遍历时,必须使用一个堆栈记录回溯点,以 便将来进行回溯。以下为一个顺序栈的定义及其部
7、分操 作的实现。ntypedef struct stack /*栈结构定义*/ bintree data100; int tag100;/为栈中每个元素设置的标记,用于后序遍历 int top; /栈顶指针,指向栈顶元素,这和2章中top有区别 seqstack; nvoid push(seqstack *s,bintree t) /*进栈*/ s-data+s-top=t; nbintree pop(seqstack *s) /*出栈*/ if (s-top!=-1) s-top-;return(s-datas-top+1); elsereturn NULL;1、 二叉树前序遍历的非递归实现
8、n前序遍历一棵非空二叉树t 时,访问完t的根结点后 ,就应该进入t的左子树,但此时必须将t保存起来 ,以便访问完其左子树后,通过t的RCHILD再进入 其右子树的访问,即在t处必须设置一个回溯点;对 t的左子树和右子树的遍历也是如此。仔细观察不难 发现,这些回溯点应该使用栈来进行管理。在整个 二叉树前序遍历的过程中,程序要做的工作始终分 成两个部分:当前正在处理的树(子树)和保存在 栈中待处理的部分,只有这两部分的工作均完成后 ,程序方能结束。非递归实现二叉树的前序遍历nvoid preorder1(bintree t) /*非递归实现二叉树的前序遍历*/ seqstack s;s.top=-
9、1;while (t) | (s.top!=-1) /*当前处理的子树不为空或栈不为空则循环*/ while (t) printf(“%c “,t-data); s.top+;s.datas.top=t; t=t-lchild;if (s.top-1) t=pop(t=t-rchild; 2、 二叉树中序遍历的非递归实现n 中序遍历一棵非空树t时 ,首先应该进入t的左 子树访问,此时由于t的根结点及右子树尚未访问 ,因此必须将t保存起来,放入栈中,以便访问完 其左子树后,从栈中取出t,进行其根结点及右子 树的访问;对t的左子树和右子树的遍历也是如此 。在整个二叉树中序遍历的过程中,程序要做的
10、工作始终分成两个部分:当前正在处理的树(子 树)和保存在栈中待处理的部分,只有这两部分 的工作均完成后,程序方能结束。n void inorder1(bintree t) seqstack s;s.top=-1;while(t!=NULL) | (s.top!=-1) while (t) push( t=t-lchild; if (s.top!=-1) t=pop(printf(“%c “,t-data);t=t-rchild; 3、二叉树后序遍历的非递归实现 n 后序遍历一棵非空树t时,首先应该进入t的左子树访问,此时 由于t的右子树及根结点尚未访问,因此必须将t保存在栈中,以 便访问完其左
11、子树后,从栈中取出t,进行其右子树及根结点的 访问。n值得注意的是,当一个元素位于栈顶即将被处理时,其左子树的 访问一定已经完成,如果其右子树尚未遍历,接下来应该进入其 右子树的访问,而此时该栈顶元素是不能出栈的,因为其根结点 还未被访问;只有等到其右子树也访问完成后,该栈顶元素才能 出栈,并输出其根结点的值。因此一个元素位于栈顶时,必须设 法识别其右子树是否已被访问。n解决的方法为:使用seqstack类型中的数组tag, 用 于标识栈中每个元素的状态: 每个元素刚进栈时,其tag值初始化为0; 当某一元素位于栈顶即将被处理时:(1)如果其tag值为0,意味着其右子树尚未访问 ,于是将其右子
12、树作为当前处理的对象,此时该栈顶元素仍应该保留在栈中,并将其tag的值改为1;(2)如果其tag值为1,意味着其右子树已被访问 , 接下来应该访问其根结点,并将其出栈。 n在整个二叉树后序遍历的过程中,程序要做的工作 始终分成两个部分:当前正在处理的树(子树)和 保存在栈中待处理的部分。只有这两部分的工作均 完成后,程序方能结束。void postorder1(bintree t) seqstack s;s.top=-1;while (t)|(s.top!=-1) while (t) s.top+;s.datas.top=t;s.tags.top=0;t=t-lchild; n while (
13、s.top-1)printf(“%c “,t-data);s.top-;if (s.top-1) t=s.datas.top;s.tags.top=1;t=t-rchild;else t=NULL;75 二叉树其它运算的实现n由于二叉树本身的定义是递归的,因此关于二叉树的许多 问题或运算采用递归方式实现非常地简单和自然。 1、二叉树的查找locate(t,x)bintree locate(bintree t, datatype x) bintree p;if (t=NULL) return NULL;else if (t-data=x) return t;else p=locate(t-lch
14、ild,x);if (p) return p;else return locate(t-rchild,x);n2 统计二叉树中结点的个数numofnode(t) int numofnode(bintree t) if (t=NULL) return 0;elsereturn(numofnode(t-lchild)+numofnode(t-rchild)+1);n3 、判断二叉树是否等价isequal(t1,t2)int isequal(bintree t1, bintree t2) int t;t=0;if (t1=NULL else if (t1!=NULL return(t);n4、 求二
15、叉树的高(深)度depth(t)int depth(bintree t) int h,lh,rh;if (t=NULL) h=0; else lh=depth(t-lchild); rh=depth(t-rchild); if (lh=rh) h=lh+1; else h=rh+1;return h; 7.6 穿线二叉树 n7.6.1 穿线二叉树的定义所谓穿线二叉树,即在一般二叉树的基础上, 对每个结点进行考察。若其左子树非空,则其左 指针不变,仍指向左子女;若其左子树为空,则 让其左指针指向某种遍历顺序下该结点的前驱; 若其右子树非空,则其右指针不变,仍指向右子 女;若其右子树为空,则让其右指针指向某种遍 历顺序下该结点的后继。如果规定遍历顺序为前 序,则称为