求解释，中序遍历二叉树的非递归算法解决方案

求解释，中序遍历二叉树的非递归算法
中序遍历二叉树的非递归算法
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();
        }
    }
}

求解释，中序遍历二叉树的非递归算法解决方案

相关推荐