Question

C++用栈实现二叉树前序遍历的算法及判断条件

我想知道文字描述的前序遍历（使用栈）
以下是别人写的一个程序，感觉他的判断条件有点奇怪，没问题说明下，有问题帮忙改下
void PreOrder2(BiTree T){
stack<BiTree> stack;
//p是遍历指针
BiTree p = T;
//栈不空或者p不空 时循环
while(p || !stack.empty()){
if(p != NULL){
//存入栈中
stack.push(p);
//打印根节点
printf("%c ",p->data);
//遍历左子树
p = p->lchild;
}
else{
//退栈
p = stack.top();
stack.pop();
//访问右子树
p = p->rchild;
}
}//while
}

Answer 1

这代码没什么问题啊，而且每一步注释也都写了，不明白你哪里看不懂？
p不空就是要遍历以p为根的子树，那么先访问根，然后遍历p的左子树；p为空但栈不空就表示以栈顶元素为根的树的左子树已经遍历完了，然后把栈顶元素取出来并退栈，遍历它的右子树。

追问

既然while里面还要判断p是否为空，while这次判断是不是太繁琐了（我知道这里有意义），不知道会不会出bug。 这样写真的好吗？

追答

这里不是繁琐或意义的问题，而是他的方法在逻辑上就要这么写啊，当遍历完整颗树T的左子树后，要把根结点出栈然后遍历右子树，此时p不为空但是栈为空，要是在while条件中不判断p，这里就停止循环了啊，也就不会遍历右子树了。