后序遍历的非递归实现

 1 //  实现后序遍历的非递归
 2 //  核心：一个结点需要弹出两次,第一次弹出的时候还需要放回原位（左子树遍历完毕）,第二次弹出的时候才输出其值（右子树遍历完毕）；
 3 
 4 
 5 #include <iostream>
 6 #include <stack>
 7 using namespace std;
 8 
 9 struct node {
10     int data;
11     struct node* left = nullptr;
12     struct node* right = nullptr;
13     int times = 0;  //当计数值到达2时，不再进入栈中;
14 };
15 
16 typedef struct node node;
17 
18 void init(node& head) {
19     head.data = 1;
20 
21     head.left = new node();
22     head.left->data = 2;
23 
24     head.left->left = new node();
25     head.left->left->data = 3;
26 
27     head.left->left->left = new node();
28     head.left->left->left->data = 4;
29 
30     head.left->right = new node();
31     head.left->right->data = 5;
32 
33     head.left->right->left = new node();
34     head.left->right->left->data = 6;
35 
36     head.right = new node();
37     head.right->data = 7;
38 }
39 
40 int main() {
41     node head;
42 
43     init(head);
44 
45     stack<node*> s;
46 
47     node* p = &head;
48 
49     while (p != nullptr || !s.empty()) {
50         // 入栈
51         if (p != nullptr) {
52             s.push(p);
53             p = p->left;
54         }
55 
56         // 出栈
57         if (p == nullptr) {
58             p = s.top();
59             s.pop();
60 
61             p->times++;
62 
63             //遍历右子树
64             if (p->times == 1) {
65                 s.push(p);
66                 p = p->right;
67             }
68 
69             //p.times==2; 继续弹栈
70             else {
71                 cout << p->data;
72                 p = nullptr;   // 回溯的关键步骤
73             }
74         }
75     }
76 
77     return 0;
78 }

关键点：

当该结点为非空，进行访问左结点；
当这个元素出栈时，需要考虑其访问次数：如果次数为1，那么需要将其再次入栈，然后遍历右子树。如果次数为2，那么表示以该节点为跟的子树访问完毕，置为null。
上述的核心遍历代码是对不同的结点以出栈和入栈为单位（遇到非空，进行入栈；遇到空，进行出栈，并进行完整的后序操作），每一次循环对一个结点进行一次完整的操作。而下列代码主要是以一次操作为单位。

 1 while (p != nullptr || !s.empty()) {
 2         if (p == nullptr) {
 3             p = s.top();
 4             s.pop();
 5             p->times++;
 6         }
 7         else {
 8             // 该结点为根的树已经遍历，相当于NULL 
 9             if (p->times == 2) {
10                 cout << p->data << " ";
11                 p = nullptr;
12             }
13             else if(p->times==1) {
14                 s.push(p);
15                 p = p->right;
16             }
17             else {
18                 s.push(p);
19                 p = p->left;
20             }
21         }
22     }