SE206---Object-Oriented-Programming/binaryTreeExpressions.cpp at main · nosferatu0205/SE206---Object-Oriented-Programming · GitHub

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;

const int N = 101;
int a[N];
// Array for storing and printing of order
vector<int> postOrder; // post order
vector<int> preOrder; // pre order
vector<int> inOrder; // in order


// function for generation of preorder expression
void preOrderGenerator(int cur,int node_t){

	if(cur >= node_t) return;
	if(a[cur] == -1) return;

	preOrder.push_back(a[cur]);

	//1st recursive call -> for right to left traversal
	preOrderGenerator(2*cur,node_t);
	//2nd recursive call -> for left to right traversal
	preOrderGenerator(2*cur+1,node_t);
}

// function for generation of postorder expression
void postOrderGenerator(int cur, int node_t){

	if (cur >= node_t) return;
	if (a[cur] == -1) return;

	postOrderGenerator(2*cur,node_t);
	postOrderGenerator(2*cur+1,node_t);

	postOrder.push_back(a[cur]);
}

// function for generation of in order expression
void InOrderGenerator(int cur, int node_t){

	if (cur >= node_t) return;
	if (a[cur] == -1) return;


	InOrderGenerator(2*cur,node_t);

	inOrder.push_back(a[cur]);

	InOrderGenerator(2*cur+1,node_t);


}


int main (){

	int n;
	cin>>n;

	int b_occur = 1;
	int actualp = 0;

	while (1){
		int x;
		cin>>x;

		if (x==-1){
			a[b_occur++] = x;
		}
		else {
			a[b_occur++] = x;
			actualp++;
		}
		if (actualp == n) break;
	}

	for (int i = 1; i<b_occur;i++){

		printf("%4d ",a[i]);
	}
	puts("");
	for (int i=1;i<b_occur;i++){
		printf("%4d ",i);
	}
	puts("");

	preOrderGenerator(1,b_occur);

	printf("Pre order : ");
	for (int x : preOrder) printf("%4d ",x) ;
	puts("");

	postOrderGenerator(1,b_occur);

	printf("Post order : ");
	for (int x : postOrder) printf("%4d ",x) ;
	puts("");

	InOrderGenerator(1,b_occur);

	printf("In order : ");
	for (int x : inOrder) printf("%4d ",x) ;
	puts("");
}