二叉树遍历非递归写法

数据结构考试前闲的蛋疼，整理课本。

结点建立

struct node
{
    int v;
    struct node* left, *right;
    int flag; //后序遍历
};
node * root;

中序遍历

模拟深搜过程，在第一次回溯的时候输出，即为中序遍历

 1 stack<node *> Q1;
 2     node * pre = root; 
 3     while (1)
 4     {
 5         while (pre!=NULL)
 6         {
 7             Q1.push(pre);
 8             pre = pre->left;
 9         } 
10         // 一直往左走
11         do
12         {
13             pre = Q1.top();
14             cout << pre->v<<" ";Q1.pop();
15         }while(pre->right==NULL&&!Q1.empty()); 
16         // 回溯到能往左走
17         if (pre->right==NULL) break;
18         // 结束的条件是 回溯到 队列为空了，还没找到能往左走的结点
19         // PS:结束上述循环的两种情况，①队列为空 ②回溯到能走的结点
20         pre = pre->right;
21     }
22     cout << endl;

中序遍历非递归

先序遍历

模拟深搜过程，在第一次加入栈的时候输出

 1 //与中序遍历相当类似
 2 stack<node *> Q3;
 3      pre = root;
 4     while (1)
 5     {
 6         while (pre!=NULL)
 7         {
 8             cout << pre->v<<" ";Q3.push(pre);
 9             pre = pre->left;
10         }
11         do
12         {
13             pre = Q3.top();
14             Q3.pop();
15         }while(pre->right==NULL&&!Q3.empty());
16         if (pre->right==NULL) break;
17         pre = pre->right;
18     }
19     cout << endl;
20 
21 先序遍历非递归

先序遍历非递归

后序遍历

和以上两个遍历的区别是

中序遍历和先序遍历，节点输出位置容易判断

先序是：在加入新节点之前

中序是：在加入右儿子之前或没有右儿子时

而对于后序遍历

没有右儿子或右儿子已经被遍历完成

中序遍历在第一次回溯之后，完全可以将根节点pop，这样就会避免重复访问，并且也已经输出了。但是对于后序遍历，是在第二遍回溯之后输出，所以不能pop。正因如此，回溯过程无法判断当前节点是第几次回溯，所以需要一个标志变量FLAG。

 1 stack<node *> Q2;
 2     pre = root;
 3     while (1)
 4     {
 5         while (pre!=NULL)
 6         {
 7             Q2.push(pre);
 8             pre = pre->left;
 9         }
10         //一直往左走
11         while(!Q2.empty()&&(pre = Q2.top())&&(pre->right==NULL||pre->flag == 1))
12         {
13             cout << pre->v<<" ";
14             Q2.pop();
15         }
16         // 回溯到能往右走，不能往右走的原因有，没有右儿子，右结点已经被访问
17         // do-while 和 while 的区分！
18         if (Q2.empty()) break;
19         // 搜索结束条件
20         pre->flag = 1;
21         pre = pre->right;
22     }
23     cout << endl;

后序遍历非递归

刚写完博客，想了一会，发现可以不用FLAG，但是需要再开一个栈来维护。

中心思想就是，后序遍历的第二次（从右结点）回溯输出和没有右儿子，都可以总结为：不能再走了就输出！

那么将深搜顺序(按先序遍历压栈)一直压入另一个栈中，当一个节点无路可走了那么输出。

那么问题来了，怎么根据一个新栈来判断他是否无路可走了呢？

直接贴代码：

 1 stack <node *> Q1;
 2     stack<node *> Q3;
 3     pre = root;
 4     node * outp ;
 5     node * Before_out;
 6     int cnt = 0;
 7     while (1)
 8     {
 9         cnt++;
10         while (pre!=NULL)
11         {
12             Q1.push(pre);
13             Q3.push(pre);
14             pre = pre->left;
15         }
16         do
17         {
18             pre = Q1.top();
19             Q1.pop();
20         }while(pre->right==NULL&&!Q1.empty());
21         // 对一个节点进行dfs到最深，并回溯。直到遇见有右儿子的节点
22         // 可以证明对于pre来说，她的左儿子没有一个点有右儿子，并且左儿子全都位于Q3中
23         while(!Q3.empty()&&(outp = Q3.top())&& (outp -> right == NULL || outp -> right == Before_out  ) )
24               {
25                   cout << outp->v <<" ";
26                   Q3.pop();
27                   Before_out = outp;
28               }
29         //上述循环，会把pre那一堆没有右儿子的（左儿子生的后代）全部倒序（回溯顺序）输出
30         if (pre->right==NULL) break;
31         pre = pre->right;
32         //之后Q3中会存着pre pre->right;
33         //当处理完pre->right(假设已经处理完成，或假设压根pre->right就只一个节点)，之后将会 倒序输出这两个点！
34          // cout << endl; 用打印标记理解更好
35     }
36     cout << endl;

非递归非FLAG后序遍历

并且可以看出，外层循环次数是右儿子个数+1；