http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
using
namespace
std;
9
10
struct
node {
11
char
data;
12
struct
node *left, *
right;
13
node() : data(
0
), left(NULL), right(NULL) { }
14
node(
int
d) : data(d), left(NULL), right(NULL) { }
15
};
16
17
18
void
prints(node *
root) {
19
if
(!root)
return
;
20
prints(root->
left);
21
cout << root->data <<
"
"
;
22
prints(root->
right);
23
}
24
25
node *buildtree(
char
in
[],
char
pre[],
int
beg,
int
end) {
26
static
int
preindex =
0
;
27
if
(beg > end)
return
NULL;
28
node *root =
new
node(pre[preindex++
]);
29
int
index =
beg;
30
for
(
int
i = beg; i <= end; i++
) {
31
if
(
in
[i] == root->
data) {
32
index =
i;
33
break
;
34
}
35
}
36
root->left = buildtree(
in
, pre, beg, index-
1
);
37
root->right = buildtree(
in
, pre, index+
1
, end);
38
return
root;
39
}
40
41
int
main() {
42
char
in
[
6
] = {
'
D
'
,
'
B
'
,
'
E
'
,
'
A
'
,
'
F
'
,
'
C
'
};
43
char
pre[
6
] = {
'
A
'
,
'
B
'
,
'
D
'
,
'
E
'
,
'
C
'
,
'
F
'
};
44
int
len =
6
;
45
node *root = buildtree(
in
, pre,
0
, len-
1
);
46
prints(root);
47
return
0
;
48
}
Data Structure Binary Tree: Construct Tree from given Inorder and Preorder traversals
