二叉树非递归后序遍历

2014-06-16

翻到自己以前考研时发过的帖子,真心觉得那时候比现在牛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; } } }