先序遍历二叉树的非递归算法

Question

6.37
void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法
{
InitStack(S);
Push(S,T); //根指针进栈
while(!StackEmpty(S))
{
while(Gettop(S,p)&&p)
{
visit(p->data);
push(S,p->lchild);
} //向左走到尽头
pop(S,p);
if(!StackEmpty(S))
{
pop(S,p);
push(S,p->rchild); //向右一步
}
}//while
}//PreOrder_Nonrecursive

Answer 1

InitStack(S);//初始化栈
p=T;//取栈顶
while(P||!StackEmpty(S)){ //P存在或者栈非空
if(p) { //p非空，即左子树或者右子树存在
Push(S,p); //将左子树入栈
p=p->lchild; //取下一个左子树
}
else{
Pop(S,p); //出栈，相当于先序遍历了，因为左子树都TMD入栈了，现在反向输出
p=p->rchild; //弹出一个左子树，就同时取其右子树右子树，然后又跳到这个if的最开头那里，p存在的那个分支。接下来再取右子树的左子树
}
}

//其实，用递归也许你更能理解一些。但是，递归本质上也是压栈，只不过是程序压栈，还不如这个效率高

Answer 2

你的这个算法 有误吧 倒数第二个，也就是倒数第8行的 pop操作是多余的