二叉树非递归后序遍历
source link: https://www.zenlife.tk/%E4%BA%8C%E5%8F%89%E6%A0%91%E9%9D%9E%E9%80%92%E5%BD%92%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86.md
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
二叉树非递归后序遍历
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; } } }*>
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK