Question

有关二叉树中序遍历严蔚敏算法的问题，百思不得其解，为什么用了两个POP？

Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
InitStack(S);
Push(S,T); //根指针进栈
while(!StackEmpty(s))
{
while(GetTop(S,p)&&p)
Push(S,p->lchild); //向左走到尽头
Pop(S,p); //空指针退栈
if(!StackEmpty(S)) //访问结点，向右一步
{
Pop(S,p);
if(!Visit(p->data))
return ERROR;
Push(S,p->rchild);
}//if
}//while
return OK;
}//InOrderTraverse 算法一
-----------------
我不懂的是第一个POP后，等于POP了空节点，栈顶应该是树的最左端节点

那么再执行第二个POP后，应该是把最左端节点也POP出去了，接下来才执行VISIT函数

那么就等于最左端的节点没有访问，直接访问了最左端节点的双亲，再去访问它的右兄弟了，而中序遍历的顺序是左---中---右，这样不是把左节点遗漏了吗？
当把P节点POP掉后，再执行visit函数，难道是对已经pop掉的节点再执行visit而不是对栈顶元素visit？可是这样一来，前序遍历的非递归算法中只用了一次pop后就开始visit，难道不是对空节点visit吗？这样一来就显得很矛盾了

Answer 1

你好，你给你算法是错误的。网上搜一下中序非递归遍历就有完整算法。错误的点while(GetTop(S,p)&&p)后应该有if（p！=null）的判断语句，这样就没有退空结点的情况。关于你的问题，先退结点再访问是没有问题的。前序遍历是从根节点开始访问，不存在访问空节点的说法。

Answer 2

要敢于怀疑书本，这个方法是错的。

追问

也就是说用了两个POP确实是错误的？

追答

我们老师教的是下面这个，我也是学生。并没有用到两POP。
/* 二叉树中序遍历的非递归实现*/
void inorder1(bintree t)
{
seqstack s;
s.top=-1;
while((t!=NULL) || (s.top!=-1))
{
while (t)
{
push(&s,t);
t=t->lchild;
}
if (s.top!=-1)
{
t=pop(&s);
printf("%c ",t->data);
t=t->rchild;
}
}
}

Answer 3

那个最左边的结点出栈，但是有返回值p，即指向该出栈结点的指针，然后visit（p—>data）就是访问了最左边的结点，我也刚刚看了这个……

Answer 4

大哥。if(!Visit(p->data))不就访问了最左端节点了吗