二叉树非递归遍历问题

来源:百度知道 编辑:UC知道 时间:2024/07/05 18:00:38
int PostOrderTraverse(BitTree &T,int (*Visit)(TElemType e)){
SqStack S;
SElemType P;//栈的元素,类型为SElemType,即BitTree
CreateStack(S);//构造堆栈
Push(S,T);//根结点进栈时
while(!StackEmpty(S)){
while(GetTop(S,P)&&P) Push(S,P->lchild);//向左走到尽头
Pop(S,P);//空指针退栈,此时P指向空指针
if(!StackEmpty(S)){
Pop(S,P); //栈顶元素退栈,并返回给P,P指向退出的栈顶值
Push(S,P->rchild);
//判断右结点是否为空
if(!P){
Pop(S,P);
if(!Visit(P->data)) return ERROR;
printf("\t");
Pop(S,P);//以访问的点退栈
GetTop(S,P);//得上一次的父母结点
Push(S,P->rchild);
}//if
}//if
else{
if(!Visit(P->data)) return ERROR;
}//else
}//while
return OK;
}//PostOrderTraverse

我的后序遍历很有问题,搞了很晚都死循环或不工作。

请大虾指教,并指出小弟出错原因,不胜感激。
问题:
我的后序遍历很有问题,不是死循环就是不工作。
请大虾指教,并指出小弟出错原因,不胜感激。

由于程序超过字符数限定,所以转载在我的博客上,请指教,谢谢。

/////////////////////////////////////////----非递归实现后序遍历------////////////////
template <class T>
void BinaryTree<T>::unPostOrder( void(*Visit)(BinaryTreeNode<T> *u ),BinaryTreeNode<T> *t)
{
Stract<BinaryTreeNode<T>*>OPR(100); //借助栈实现后序遍历
BinaryTreeNode<T>*p;
while(t!=NULL)
{
OPR.Add(t);
t=t->LeftChild;
}
while(!OPR.Isempty())
{
p=OPR.Top();
if(p->RightChild!=NULL)
{
t=p->RightChild;
while(t!=NULL)
{
OPR.Add(t);
t=t->LeftChild;
}

Visit(p);
}
else
{
Visit(p);
}
}

}