7.4 二叉树的遍历 7.4.1 二叉树遍历的定义 所谓二叉树的遍历，是指按一定的顺序对二叉 树中的每个结点均访问一次，且仅访问一次。 按照根结点访问位置的不同，通常把二叉树的 遍历分为六种：TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左）LRT（左右根）, RLT（右左根）n其中，TRL、RTL和RLT三种顺序在左右子树之间均 是先右子树后左子树，这与人们先左后右的习惯不 同，因此，往往不予采用。余下的三种顺序TLR、 LTR和LRT根据根访问的位置不同分别被称为前序遍 历、中序遍历和后序遍历。 （1）二叉树的前序遍历首先访问根结点；然后按照前序遍历的顺序访问根结点的左子树；再按照前序遍历的顺序访问根结点的右子树。（2）二叉树的中序遍历 首先按照中序遍历的顺序访问根结点的左子树； 然后访问根结点； 最后按照中序遍历的顺序访问根结点的右子树。（3）二叉树的后序遍历 首先按照后序遍历的顺序访问根结点的左子树； 然后按照后序遍历的顺序访问根结点的右子树； 最后访问根结点。abdfegc前序遍历：前序遍历：abdefgcabdefgc中序遍历中序遍历: : debgfacdebgfac后序遍历后序遍历: : edgfbcaedgfbca练习！G HA图 5-15D E FB C前序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCA练习！n下面我们再给出一种遍历二叉树的方法n （1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。D G B A E C H F G HD E FB CA图 5-167.4.2 二叉树遍历的递归实现 由于二叉树的遍历是递归定义的，因此采用递 归方式实现二叉树遍历的算法十分方便，只要按 照各种遍历规定的次序，访问根结点时就输出根结点 的值，访问左子树和右子树时进行递归调用即可。1 、前序遍历二叉树的递归算法 void preorder(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); 4 、二叉树的创建算法 n 利用二叉树前序遍历的结果可以非常方便地生成给定的 二叉树，具体做法是：将第一个输入的结点作为二叉树的 根结点，后继输入的结点序列是二叉树左子树前序遍历的 结果，由它们生成二叉树的左子树；再接下来输入的结点 序列为二叉树右子树前序遍历的结果，应该由它们生成二 叉树的右子树；而由二叉树左子树前序遍历的结果生成二 叉树的左子树和由二叉树右子树前序遍历的结果生成二叉 树的右子树的过程均与由整棵二叉树的前序遍历结果生成 该二叉树的过程完全相同，只是所处理的对象范围不同， 于是完全可以使用递归方式加以实现。nvoid createbintree(bintree *t) char ch;if (ch=getchar()= ) *t=NULL;else *t=(bintnode *)malloc(sizeof(bintnode); /*生成二叉树的根结点*/(*t)-data=ch;createbintree( /*递归实现左子树的建立*/createbintree( /*递归实现右子树的建立*/ 7.4.3 二叉树遍历的非递归实现 n第5章介绍了由递归程序转换成非递归程序的两种方法 ：简单递归程序的转换和复杂递归程序的转换；n二叉树的遍历问题应该属于后者，即在采用非递归方式 实现二叉树遍历时，必须使用一个堆栈记录回溯点，以 便将来进行回溯。以下为一个顺序栈的定义及其部分操 作的实现。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、 二叉树前序遍历的非递归实现n前序遍历一棵非空二叉树t 时，访问完t的根结点后 ，就应该进入t的左子树，但此时必须将t保存起来 ，以便访问完其左子树后，通过t的RCHILD再进入 其右子树的访问，即在t处必须设置一个回溯点；对 t的左子树和右子树的遍历也是如此。仔细观察不难 发现，这些回溯点应该使用栈来进行管理。在整个 二叉树前序遍历的过程中，程序要做的工作始终分 成两个部分：当前正在处理的树（子树）和保存在 栈中待处理的部分，只有这两部分的工作均完成后 ，程序方能结束。非递归实现二叉树的前序遍历nvoid preorder1(bintree t) /*非递归实现二叉树的前序遍历*/ seqstack s;s.top=-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的左子树和右子树的遍历也是如此 。在整个二叉树中序遍历的过程中，程序要做的 工作始终分成两个部分：当前正在处理的树（子 树）和保存在栈中待处理的部分，只有这两部分 的工作均完成后，程序方能结束。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保存在栈中，以 便访问完其左子树后，从栈中取出t，进行其右子树及根结点的 访问。n值得注意的是，当一个元素位于栈顶即将被处理时，其左子树的 访问一定已经完成，如果其右子树尚未遍历，接下来应该进入其 右子树的访问，而此时该栈顶元素是不能出栈的，因为其根结点 还未被访问；只有等到其右子树也访问完成后，该栈顶元素才能 出栈，并输出其根结点的值。因此一个元素位于栈顶时，必须设 法识别其右子树是否已被访问。n解决的方法为：使用seqstack类型中的数组tag, 用 于标识栈中每个元素的状态： 每个元素刚进栈时，其tag值初始化为0； 当某一元素位于栈顶即将被处理时：（1）如果其tag值为0，意味着其右子树尚未访问 ，于是将其右子树作为当前处理的对象，此时该栈顶元素仍应该保留在栈中，并将其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 (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-lchild,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、 求二叉树的高(深)度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 穿线二叉树的定义所谓穿线二叉树，即在一般二叉树的基础上， 对每个结点进行考察。若其左子树非空，则其左 指针不变，仍指向左子女；若其左子树为空，则 让其左指针指向某种遍历顺序下该结点的前驱； 若其右子树非空，则其右指针不变，仍指向右子 女；若其右子树为空，则让其右指针指向某种遍 历顺序下该结点的后继。如果规定遍历顺序为前 序，则称为