-
Notifications
You must be signed in to change notification settings - Fork 0
/
btree.c
116 lines (97 loc) · 2.38 KB
/
btree.c
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
115
116
#include "btree.h"
#include "stdlib.h"
#include "input_token.h"
#include <stdio.h>
struct treenode {
int data; //if toktype == Operand, data holds the value of the operand
//int toktype;
struct treenode *left;
struct treenode *right;
};
/*
int eval_children_leaves(BTree t) {
if(isLeaf(t->left) && isLeaf(t->right)) {
switch(t.toktype) {
case Plus:
return t.left.data + t.right.data;
case Minus:
return t.left.data - t.right.data;
case Mult:
return t.left.data * t.right.data;
case Divide:
return t.left.data / t.right.data;
}
}
*/
int eval (BTree t) {
if(is_leaf(t))
return t->data; //return data when hit any leaf of the tree, as base case
int left = eval(t->left); //recursively evaluate left subtree
int right = eval(t->right); //recursively evaluate right subtree
return calc_operands(left, t->data, right); //left and right have been evaluated, calculate operands
}
int calc_operands(int left, int opr, int right) {
switch(opr) {
case Plus:
return left + right;
case Minus:
return left - right;
case Mult:
return left * right;
case Divide:
return left / right;
}
}
//return 1 if true, 0 if false
int is_leaf(BTree node) {
if (node->left == NULL && node->right == NULL)
return 1;
else
return 0;
}
void in_order_traversal( BTree t ) {
if(is_leaf(t)) {
printf("%d", t->data);
return;
}
printf("(");
in_order_traversal(t->left);
switch(t->data) {
case Plus: printf(" + "); break;
case Minus: printf(" - "); break;
case Divide: printf(" / "); break;
case Mult: printf(" * "); break;
}
in_order_traversal(t->right);
printf(")");
}
void post_order_traversal( BTree t ) {
if(is_leaf(t)) {
printf("%d ", t->data);
return;
}
post_order_traversal((t->left));
post_order_traversal((t->right));
switch(t->data) {
case Plus: printf(" + "); break;
case Minus: printf(" - "); break;
case Divide: printf(" / "); break;
case Mult: printf(" * "); break;
}
}
BTree create_node_leaf(int w) {
struct treenode *node;
node = (struct treenode *) malloc(sizeof (struct treenode));
node->left = NULL;
node->right = NULL;
node->data = w;
return node;
}
BTree create_node_children(BTree left, int w, BTree right) {
struct treenode *node;
node = (struct treenode *) malloc(sizeof (struct treenode));
node->left = left;
node->right = right;
node->data = w;
return node;
}