二叉树非递归后序遍历

2014-06-16

翻到自己以前考研时发过的帖子,真心觉得那时候比现在牛B多了...

网上传的很多二叉树非递归遍历的算法,都是在结点中加了一个标记的,第二次访问到的时候才访问。这是我以前自己写过的一个版本,真可谓终极精简版。只用了一个循环,而且也没有在结点上加标记。

二叉树后序遍历和中序遍历几乎是一模一样的,唯一的区别是出栈访问时加了条件:无右子树或者右子树已访问过。

Node* lastvisit;   //标记最后一次访问的结点
stack<Node*> s;
Node* p=root;   //root是根结点
while(p || !s.empty())
{
        if(p)
        {
            s.push(p);
            p=p->lchild;
        }
        else
        {
            p=s.top();
            if(!p->rchild || p->rchild==lastvisit)   //满足条件才访问
            {
                s.pop();
                cout<<p->data;
                lastvisit=p;          //访问完后有清理工作
                p=0;
                continue;    
            }
            p=p->rchild;
        }
    }
}