http://www.geeksforgeeks.org/morris-traversal-for-preorder/
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
while
(root) {
20
if
(root->left ==
NULL) {
21
cout << root->data <<
"
"
;
22
root = root->
right;
23
}
24
else
{
25
node* cur = root->
left;
26
while
(cur->right && cur->right != root) cur = cur->
right;
27
if
(cur->right ==
NULL) {
28
cout << root->data <<
"
"
;
29
cur->right =
root;
30
root = root->
left;
31
}
32
else
{
33
cur->right =
NULL;
34
root = root->
right;
35
}
36
}
37
}
38
}
39
40
int
main() {
41
node *root =
new
node(
1
);
42
root->left =
new
node(
2
);
43
root->right =
new
node(
3
);
44
root->left->left =
new
node(
4
);
45
root->left->right =
new
node(
5
);
46
root->right->left =
new
node(
6
);
47
root->right->right =
new
node(
7
);
48
root->left->left->left =
new
node(
8
);
49
root->left->left->right =
new
node(
9
);
50
root->left->right->left =
new
node(
10
);
51
root->left->right->right =
new
node(
11
);
52
prints(root);
53
return
0
;
54
}
