6.4二叉树的遍历算法描述

6.4二叉树的算法描述VoidlnorderTraverse(BiTreeBT){／／采用二叉链表存储结构，中序遍历二叉树T的非递归算法.InitStack(S)；p=BT；while(p||!StackEmpty(S)){if(p){push(S，p)；p=p-lchild；}//根指针进栈，遍历左子树else{／／根指针退栈，访问根结点，遍历右子树pop(S，p)；visit(p));p=p-rchild；}//else}／／InOrderTraverse6.4.1非递归中序遍历BT的算法:我们先观察一下三种遍历行走的路线ABCEFHGDI*********前序遍历NLR#########ABCEFHGDI中序遍历LNR&&&&&&&&&ABCEFHGDI*********#########三种遍历的访问位置对比：三种遍历的路线完全一样，只是访问时间不同；前序：第一次经过*时访问中序：第二次经过#时访问后序：第三次经过&时访问遍历线路的核心规则是：先左后右；我们用一个栈stack记录走过的位置，以便返回；stack中数据元素的类型：*BiTNode(或BiTree)函数：BiTreeP;push(S,p);pop(S,p);BooleanStackEmpty(S);下面给出基于逻辑结构的算法描述非递归中序遍历二叉树的算法思想建立栈stack；1.P指向根；2.当p不空且stack不空时反复做：若p不空,p入栈;p指向左子女；否则：•出栈顶元素到p中；•访问p；•p指向右子女；4.结束ABCDEFGpi&A(1)非递归中序遍历BT的算法:ABCDEFGpi&A&B&C(3)非递归中序遍历BT的算法:p=NULLABCDEFGi&A&B访问：C(4)非递归中序遍历BT的算法:pABCDEFGi&A访问：CB(5)非递归中序遍历BT的算法:ABCDEFGi&A&D访问：CBp(6)非递归中序遍历BT的算法:ABCDEFGi&A&D&E访问：CBp(7)非递归中序遍历BT的算法:ABCDEFGi&A&D访问：CBEp(8)非递归中序遍历BT的算法:ABCDEFGi&A&D&G访问：CBEP=NULL(9)非递归中序遍历BT的算法:ABCDEFGi&A&D访问：CBEGp(10)非递归中序遍历BT的算法:ABCDEFGi&A访问：CBEGDp(11)非递归中序遍历BT的算法:ABCDEFGi&A&F访问：CBEGDp(12)非递归中序遍历BT的算法:ABCDEFGi&A访问：CBEGDFp=NULL(13)非递归中序遍历BT的算法:ABCDEFGi访问：CBEGDFAp(14)非递归中序遍历BT的算法:ABCDEFGi访问：CBEGDFAp=NULL(15)非递归中序遍历BT的算法:1/21/2020二叉树与表达式：表达式:(a+b)×c–d/e二叉树的先序遍历序列为：–×+abc/de二叉树的中序遍历序列为：a+b×c–d/e二叉树的后序遍历序列为：ab+c×de/–abcde-×+/前缀表达式中缀表达式后缀表达式voidPreOrderTraverse(BiTreeT,void(*visit)(TelemType&e)){InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){if(!visit(p-data))returnERROR;//访问根结点Push(S,p);p=p-lchild;}//根指针进栈，遍历左子树else{//根指针退栈，遍历右子树Pop(S,p);p=p-rchild;}//else}//whilereturnOK;}//PreOrderTraverse非递归先序遍历二叉树6.4.2遍历算法的应用举例1、查询二叉树中某个结点1/21/2020StatusPreorderelem(BiTreeT,ElemTypex,BiTree&p){//若二叉树中存在和x相同的元素，则p指向该结点并返回trueif(T){if(T-data==x){p=T;returnOK,}else{if(Preorderelem(T-lchild,x,p)returnOK;elsereturn(Preorderelem(T-rchild,x,p));}//else}//ifelsereturnFALSE;}1/21/20202、统计二叉树中叶子结点的个数1/21/2020算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点并计数。在遍历算法中增加一个参数用于计数，并将算法中“VISIT()”的操作改为:若是叶子，则计数器增1。voidCountLeaf(BiTreeT,int&count){if(T){if((!T-lchild)&&(!T-rchild))count++;//对叶子结点计数CountLeaf(T-lchild,count);CountLeaf(T-rchild,count);}//if}//CountLeaf3按先序遍历序列建二叉树StatusCreateBiTree(BiTree&T){scanf(&ch);if(ch=='')T=NULL;else{if(!(T=newBiTNode))exit(OVERFLOW);T-data=ch;//生成根结点CreateBiTree(T-lchild);//构造左子树CreateBiTree(T-rchild);//构造右子树}returnOK;}//CreateBiTreeABCDEGFABCDEFG按先序遍历序列建立二叉树的二叉链表，已知先序序列为：1/21/20204、求二叉树的深度1/21/2020intTreeDepth(BiTreeT){//返回二叉树的深度if(!T)depth=0;else{depthLeft=TreeDepth(T-lchild);depthRight=TreeDepth(T-rchild);depth=1+(depthLeftdepthRight?depthLeft:depthRight);}returndepth;}算法：1前序遍历序列：EDACBGFH中序遍历序列：ADCBEFHG试画出满足以上序列的二叉树2中序遍历序列：ADCBHFEG后序遍历序列：ABCDEFGH试画出满足以上序列的二叉树课堂练习