woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

精典二叉树非递归遍历的算法

遍历二叉树的非递归算法
编写的方法:根据树中结点的遍历规律及顺序直接写出其非递归算法。
先序非递归算法
【思路】
假设:T是要遍历树的根指针,若T != NULL
对于非递归算法,引入栈模拟递归工作栈,初始时栈为空。
问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子树的根指针?
方法1:访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,再先序遍历T的右子树。
方法2:访问T->data后,将T->rchild入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T->rchild,出栈,遍历以该指针为根的子树。
【算法1
void    PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{    //
基于方法一,流程图如右,当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【算法2
void    PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{    //
基于方法二,流程图如右,当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
进一步考虑:对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T
是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子树。
问题:如何用栈来保存信息,使得在中序遍历过左子树后,能利用栈顶信息获取T指针?
方法:先将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,访问T->data,再中序遍历T的右子树。

【算法】
void    InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{    //
流程图如右,当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
进一步考虑:对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】

T
是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法,结点入栈时,配一个标志tag一同入栈(0:遍历左子树前的现场保护,1:遍历右子树前的现场保护)
首先将Ttag(0)入栈,遍历左子树;返回后,修改栈顶tag1,遍历右子树;最后访问根结点。
typedef struct stackElement{
Bitree    data;
char        tag;
}stackElemType;
【算法】
void    PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{    //
流程图如右,当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1);        //
设置栈顶标记
T = GetTopPointer(S);    //
取栈顶保存的指针
T = T->rchild;
}else break;
}
}

 

posted on 2009-10-10 15:00 肥仔 阅读(1452) 评论(0)  编辑 收藏 引用 所属分类: 数据结构 & 算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理