[算法]二叉树的非递归前序遍历算法
by EmilMatthew
前言:
二叉树的前序遍历算法的递归版本简洁而又好懂:
void preOrder(PBinTreeNode inNode)
{
if(inNode==NULL)
return;
else
{
preVisit(inNode->info);
preOrder(inNode->llink);
preOrder(inNode->rlink);
}
}
既然有这么好的算法，为何还要去改成非递归版本呢？原因在于，有些场和，出于性能和条件的考虑，无法使用递归机制，这就必须借助非递归来实现相应的递归算法。况且，做这样的练习对算法能力本身的训练也是相当有益的，何乐而不为之?
这里采用的非递归算法用到一个栈来做为辅助的存储空间.
核心算法思路:
检查传入的树是否为空。
访问根结点，压栈.
While(栈myStack不为空)
{
While(当前结点p有左儿子)//这个程序段执行的是从当前的结点访问至最左儿子的过程.
{
pßp->llink;
visit(p)
push(myStack,p);
}
flag=0;
While(!flag并且栈myStack不为空)
//这个程序段执行的是从当前的结点起向上找到第一个有右儿子的结点.
{
pßpop(myStack,p);
if(p->rlink!=NULL)
//当发现当前结点有右儿子时，则跳到右儿子结点上，然后跳出这个子过程，并重新执行第一步//从当前的结点访问至最左儿子的过程
{
pßp->llink;
visit(p)
push(myStack,p);
flag=1;
}
}
}
这里最关键的，就是要处理好”跳”到右儿子这个动作,在跳直前，应将原来压栈的结点给弹出，否则会出现在当前结点和其右儿子之间“跳来跳去”的死循环情况.
算法的C语言实现:
void preOrderUnStack(PBinTreeNode inNode)
{
PBinTreeNode p;
PSeqStack myStack;
int flag;
assertF(inNode!=NULL,"pass in node is null\n");
myStack=createNullSeqStack();
p=inNode;
preVisit(p->info);//visit
seqPush(myStack,p);
while(!isNullSeqStack(myStack))
{
while(p->llink!=NULL)
{
p=p->llink;//move to left child node
preVisit(p->info);//visit
seqPush(myStack,p);//push current node to the stack.
}
flag=0;
while(!flag&&!isNullSeqStack(myStack))
{
p=seqPop(myStack);
if(p->rlink!=NULL)
{
p=p->rlink;
preVisit(p->info);//visit
seqPush(myStack,p);
flag=1;
}
}
}
printf("preOrder visit end\n");
}
源码下载:
http://emilmatthew.51.net/downloads/CBTUnStack.rar
如有批评与改进意见,还望不恪赐教!
参考文献：
[1] 张乃孝.算法与数据结构.高等教育出版社.2002
|