数据结构精品课件-基于栈的递归消除.pptVIP

6.3 二叉树的遍历与线索化 第 6 章 树和二叉树 递归转换到非递归的原因： 递归的执行效率低； 运行环境没有递归机制。 递归转化的两种方法： 6.3 二叉树的遍历与线索化 第 6 章 树和二叉树 基于栈的递归消除： 6.3 二叉树的遍历与线索化 第 6 章 树和二叉树 ①中序遍历二叉树的非递归算法 基于栈的递归消除： 从根开始，当前结点存在或栈不为空，重复如下操作： 1、当前结点进栈，走左子树，直至左子树为空； 2、退栈并访问； 3、走右子树； void InOrder（BiTree root） {InitStack (S); p=root; while(p!=NULL || !IsEmpty(S)) { if (p!=NULL) /* 根指针进栈，遍历左子树 */ { Push(S,p); p=p-LChild; } else /*根指针退栈，访问根结点，遍历右子树*/ {Pop(S,p); Visit(p-data); p=p-RChild;} } } 时间复杂度：O(n) 空间复杂度：O(k) 第 6 章 树和二叉树 ①中序遍历二叉树的非递归算法 调用栈操作 ( s[m]表示栈，top表示栈顶指针) Void inorder(BiTree root) { do{ while(p!=NULL) {if (topM) return(‘overflow’); top=top+1; s[top]=p; p=p-Lchild}; /*进入左子树*/ if(top!=0) { p=s[top]; top=top-1; Visit(p-data); /*访问根结点*/ p=p-Rchild;} /*进入右子树*/ }while(p!=NULL||top!=0) } 第 6 章 树和二叉树 ①中序遍历二叉树的非递归算法 直接实现栈操作 算法思想： 从根开始，当前结点存在或栈不为空，重复如下操作： 1、当前结点进栈，走左子树，直至左子树为空； 2、如果栈顶结点右子树为空或右子树已访问过，则退 栈并访问刚退栈的栈顶结点； 3、否则，走右子树； 判定右子树是否已访问过有多种方法，在此采用：q记录刚访问过的结点，并判定栈顶结点右孩子是否为q。 后序遍历非递归较上述算法的主要区别在于：要判定是否应访问当前栈顶结点p。1. p无右孩子；2. p的右孩子已访问过，此时应访问栈顶结点p，除这两种情况外，均应进入右子树访问。 第 6 章 树和二叉树 ②后序遍历二叉树的非递归算法 void PostOrder（BiTree root） { BiTNode * p,*q； BiTree S[stack-size]； int top=0; q=NULL; p=root; while(p!=NULL || top!=0) { while(p!=NULL) { top=++; if(top=stack-size) return(‘overflow’); s[top]=p; p=p-LChild; } if(top0) { p=s[top]; if((p-RChild==NULL) ||(p-RChild==q)) { visit(p-data); q=p; top--; p=NULL; } else p=p-RChild; } } free(s); } ②后序遍历二叉树的非递归算法 第 6 章 树和二叉树