二叉树非递归后序遍历

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

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

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

Node* lastvisit; //标记最后一次访问的结点 stack 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<data; lastvisit=p; //访问完后有清理工作 p=0; continue;　　　　 } p=p->rchild; } } }