http://www.geeksforgeeks.org/level-order-traversal-in-spiral-form/
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
using
namespace
std;
7
8
struct
node {
9
int
data;
10
struct
node *left, *
right;
11
node() : data(
0
), left(NULL), right(NULL) { }
12
node(
int
d) : data(d), left(NULL), right(NULL) { }
13
};
14
15
void
print(node *
node) {
16
if
(!node)
return
;
17
print(node->
left);
18
cout << node->data <<
"
"
;
19
print(node->
right);
20
}
21
22
void
printspiral(node*
root) {
23
if
(!root)
return
;
24
bool
flag =
true
;
25
stack<node*>
S, T;
26
S.push(root);
27
while
(!
S.empty()) {
28
while
(!
S.empty()) {
29
node *top =
S.top();
30
S.pop();
31
cout << top->data <<
"
"
;
32
if
(!
flag) {
33
if
(top->left) T.push(top->
left);
34
if
(top->right) T.push(top->
right);
35
}
36
else
{
37
if
(top->right) T.push(top->
right);
38
if
(top->left) T.push(top->
left);
39
}
40
}
41
swap(S, T);
42
flag = !
flag;
43
}
44
}
45
46
47
int
main() {
48
struct
node* root =
new
node(
1
);
49
root->left =
new
node(
2
);
50
root->right =
new
node(
3
);
51
root->left->left =
new
node(
7
);
52
root->left->right =
new
node(
6
);
53
root->right->left =
new
node(
5
);
54
root->right->right =
new
node(
4
);
55
printspiral(root);
56
return
0
;
57
}
Data Structure Binary Tree: Level order traversal in spiral form
