【数据结构】树的前序、中序、后续遍历的非递归写法

理解的精髓在于用"栈"来取代递归,出栈的操作其实就相当于某层递归的出口

【前序遍历】

用栈来替代递归的过程(因为递归归根到底也是用栈来实现的)

考虑递归的时候每进入一个递归都会往左子树试探,因此一直往左子树走到头,遇到一个节点就访问它

然后压入栈中访问完左子树之后再回过头继续对每个节点的右子树进行"递归操作"

 1 void PreOrder(){
 2     Node p = root;
 3     while (p || s.empty()){
 4         while (p){
 5             s.push(p);
 6             cout<<p->idx<<" ";
 7             p = p->l;
 8         }
 9         if (!s.empty()){
10             p = s.top();
11             s.pop();
12             p = p->r;
13         }
14     }
15 }

【中序遍历】

和中序遍历结构一样,只是访问的时刻变了,只有左子树访问完了才开始访问栈中的节点(迎合中序遍历的要求)

 1 void MiddleOrder(){
 2     Node p = root;
 3     while (p || s.empty()){
 4         while (p){
 5             s.push(p);
 6             p = p->l;
 7         }
 8         if (!s.empty()){
 9             //到这一步说明s.top()的左子树访问完了(或者左子树为空)
10             p = s.top();s.pop();
11             cout<<p->idx<<" ";
12             p = p->r;
13         }
14     }
15 }

【后序遍历】

基本的思路和中序遍历、前序遍历类似。

但是需要考虑一个问题,就是当到达s.top()这个点的时候,虽然s.top()的左子树都已经访问完了。

但是不能保证s.top()的右子树访问完了。所以只有当s.top()的右子树为空,或者s.top()的右子树的根节点

已经访问过了(或者可以说前一个访问的点是s.top()的右子树的根节点,因为访问完右子树的根节点肯定就接着访问的是s.top()了),

那么就可以直接访问s.top()了,否则这个点还不到该访问的时候,因此还得入栈,递归他的右子树。

可以回忆一下递归的写法,会发现某个点x要在递归dfs(l[x])和dfs(r[x])之后才能访问(后续遍历),因此可以想见这个点s.top()需要入栈两次

之后才能保证要开始访问s.top()了，所以另一种写法是,记录这个点是第几次入栈了,如果是第二次,那么就可以等下次弹出的时候直接输出了。

代码中给的是,记录上次访问的是哪个节点,也是可以的,比较方便)

 1 void LaterOrder(){
 2     Node p = root;
 3     Node lastv = NULL;
 4     while (p || s.empty()){
 5         while (p){
 6             s.push(p);
 7             p = p->l;
 8         }
 9         if (!s.empty()){
10             p = s.top();
11             if(!p->r || p->r==lastv){//说明右子树的节点已经都访问过了
12                 cout<<p->idx<<" ";
13                 lastv = p;
14                 p=NULL;//方便往上"递归"
15             }else{
16                 p = p->r;
17             }
18         }
19     }
20 }