http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
#include <map>
9
using
namespace
std;
10
11
struct
node {
12
int
data;
13
struct
node *left, *
right;
14
node() : data(
0
), left(NULL), right(NULL) { }
15
node(
int
d) : data(d), left(NULL), right(NULL) { }
16
};
17
18
void
prints(node *
root) {
19
if
(!root)
return
;
20
stack<node*>
S;
21
do
{
22
while
(root) {
23
if
(root->right) S.push(root->
right);
24
S.push(root);
25
root = root->
left;
26
}
27
root =
S.top();
28
S.pop();
29
if
(root->right && !S.empty() && root->right ==
S.top()) {
30
S.pop();
31
S.push(root);
32
root = root->
right;
33
}
34
else
{
35
cout << root->data <<
"
"
;
36
root =
NULL;
37
}
38
}
while
(!
S.empty());
39
}
40
41
int
main() {
42
node *root =
new
node(
1
);
43
root->left =
new
node(
2
);
44
root->right =
new
node(
3
);
45
root->left->left =
new
node(
4
);
46
root->left->right =
new
node(
5
);
47
root->right->left =
new
node(
6
);
48
root->right->right =
new
node(
7
);
49
prints(root);
50
return
0
;
51
}
