求解释，中序遍历二叉树的非递归算法
中序遍历二叉树的非递归算法
void InOrderTraverse(BiTree bt){
//二叉树bt采用二叉链表存储，对bt进行中序遍历
　　if(bt){
　　 InitStack(S); Push(S, bt); //根指针进栈
　　 while(!StackEmpty(S)) {
　　 while(GetTop(S,p)&&p)
　　 Push(S, p->lchild); //向左一直走到尽头
　　 Pop(S, p); //空指针退栈
　　 if(! StackEmpty(S))
　　 { Pop(S,p); printf(p->data); Push(S, p->rchild); }
　　 } //while
　　} //if
} // InOrderTraverse

最后面Push(S, p->rchild);这一句，前面已经到了最左下角的了（假设存在这个左孩子），printf这个data之后，将rchild入栈，因为没有右孩子，入进去的是NULL，Pop出来，P就是NULL，NULL打印，再入栈右孩子。我蒙圈了，求解释这个if循环。谢谢了，老师讲的给忘了，晚上自习看不明白了。



[解决办法]
中序遍历思路应该是很明晰的啊：对于结点P，一直往左走，并把经过的结点都压栈里面，直到最左边。想想，此时这个结点是不是应该第一个访问（因为它没有左子树了）。访问这个结点，然后，判断它的右子树，如果不为空，则用同样的方式处理它的右子树。如果为空，那就从栈里面弹出来一个结点得了，栈为空就结束了。
至于代码实现，可以有两种方式：（这是我以前写的两种实现方式）

C/C++ code

//中序遍历（非递归）template<class T>void mediumOrderVisitNoRecursion(Node<T>* root){    //遇到一非空结点，则把其压入栈中，之后遍历其左子树    //结点为空，则从栈中弹出一结点，并访问    //遍历该结点的右子树    stack<Node<T>*>sta;    Node<T>* point=root;        //空树则返回    if(root==NULL){return;}    while(!sta.empty() || point!=NULL)    {        if(point!=NULL)        {            sta.push(point);            point=point->getLeft();                }        else        {            point=sta.top();            visit(point);            sta.pop();            point=point->getRight();        }    }}//中序遍历（非递归）(另一种写法）template<class T>void mediumOrderVisitNoRecursion_1(Node<T>* root){    //遇到一非空结点，则把其压入栈中，往左继续走，直至为空（走到最左侧结点）    //从栈中弹出（若栈不空）一个结点访问    //遍历该结点的右子树    stack<Node<T>*>sta;    Node<T>* point=root;    //空树则返回    if(root==NULL){return;}    while(!sta.empty() || point)    {        while(point)    //一直往右遍历，直到最左边的结点        {            sta.push(point);            point=point->getLeft();                }        point=NULL;        if(!sta.empty())        //栈不为空，取出栈顶值，访问。其实就是访问的最左边的结点        {            point=sta.top();            visit(point);            sta.pop();        }        point=point->getRight();    }    while(!sta.empty() || point!=NULL)    {        if(point!=NULL)        {            sta.push(point);            point=point->getLeft();                }        else        {            point=sta.top();            visit(point);            sta.pop();            point=point->getRight();        }    }}