-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathImplementation of expression tree and traversals
114 lines (99 loc) · 1.89 KB
/
Implementation of expression tree and traversals
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
106
107
108
109
110
111
112
113
114
Get the input postfix expression and construct an expression tree.
Traverse the constructed Expression tree by Inorder, Preorder and Postorder methods.
[Note:- Each character corresponds to a number or an operator. Use only single digit numbers.]
#include<stdio.h>
#include<stdlib.h>
struct tree
{
char data;
struct tree *left;
struct tree *right;
};
struct tree *stack[30];
int top=-1;
struct tree * newnode(char b);
void push(struct tree * temp);
struct tree * pop();
void inorder(struct tree * t);
void preorder(struct tree * t);
void postorder(struct tree * t);
int main()
{
char a[30];
struct tree * temp;
int i;
printf("Enter the postfix expression:\n");
scanf("%s",a);
for(i=0;a[i]!='\0';i++)
{
if(a[i]=='*' || a[i]=='/' || a[i]=='+' || a[i]=='-')
{
temp=newnode(a[i]);
temp->right=pop();
temp->left=pop();
push(temp);
}
else
{
temp=newnode(a[i]);
push(temp);
}
}
printf("Inorder Traversal\n");
inorder(temp);
printf("\n");
printf("Preorder Traversal\n");
preorder(temp);
printf("\n");
printf("Postorder Traversal\n");
postorder(temp);
return 0;
}
struct tree * newnode(char b)
{
struct tree *temp = (struct tree*)malloc(sizeof(struct tree));
temp->data = b;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void push(struct tree * temp)
{
if(top == 30)
return;
else{
stack[++top] = temp;
}
}
struct tree * pop()
{
if(top==-1)
return NULL;
struct tree *temp = stack[top];
top--;
return temp;
}
void inorder(struct tree * t)
{
if(t!=NULL){
inorder(t->left);
printf(" %c",t->data);
inorder(t->right);
}
}
void preorder(struct tree * t)
{
if(t!=NULL){
printf(" %c",t->data);
preorder(t->left);
preorder(t->right);
}
}
void postorder(struct tree * t)
{
if(t!=NULL){
postorder(t->left);
postorder(t->right);
printf(" %c",t->data);
}
}