-
Notifications
You must be signed in to change notification settings - Fork 0
/
Tree.cpp
89 lines (80 loc) · 1.5 KB
/
Tree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<stack.h>
struct node
{
int data;
node *left, *right;
};
node *newNode(int data)
{
node *temp = (node*)malloc(sizeof(node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
}
void iterative_preorder(node *root)
{
if(root == NULL)
return;
stack<node *>S;
S.push(root);
while(!S.empty())
{
node *temp = S.top(); S.pop();
cout<<temp->data<<" ";
if(temp->right!=NULL)
S.push(temp->right);
if(temp->left!=NULL)
S.push(temp->left);
}
}
void iterative_inorder(node *root)
{
node *current = root;
stack<node *>S;
// S.push(current);
while(true)
{
cout<<current->data<<endl;
if(current!=NULL)
{
// current = current->left;
S.push(current);
current = current->left;
} else
{
if(S.empty() == true)
break;
else
{
current = S.top(); S.pop();
if(current!=NULL)
current = current->right;
}
}
}
}
node *construct_tree(int pre[], int pres, pree, int in[], int ins)
{
if(pree<pres)
return NULL;
node *temp = newnode(in[ins]);
int index = pres;
for(int i=pres;i<=pree;i++)
if(pre[i]==in[ins])
{index = i; break}
temp->left = construct_tree(pre, pres, index-1, in, ins+1);
temp->right = construct_tree(pre, index+1, pree, in, ins+1);
return temp;
}
int main()
{
struct node *root = newNode(10);
root->left = newNode(8);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
root->right->left = newNode(2);
iterative_inorder(root);
system("pause");
}