-
Notifications
You must be signed in to change notification settings - Fork 0
/
assign12.c
96 lines (96 loc) · 2.87 KB
/
assign12.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
/*
Name: Shaurya Gupta
Roll No: 1601CS43
Date: 11/04/2017
Objective: using files, get inorder and postorder and then write preorder
*/
#include "stdio.h"
#include "stdlib.h"
typedef struct node {
struct node* left;
struct node* right;
char data;
} node;
typedef node* nodeptr;
// function to form tree given inorder and postorder as well as the indices of inorder that indicate subtree
nodeptr tree(int start, int end, int nodes, char* inorder, char *postorder, FILE* out) {
// empty subtree
nodeptr root = (nodeptr)(malloc(sizeof(node)));
if(start > end) {
return NULL;
}
// i is loop variable, splitAt is root of current subtree
int i, highestIndex = 0, splitAt;
// here we find the root of current subtree by finding the node that is farthest in postorder
for(i = start; i <= end; i++) {
int j;
for(j = 1; j <= nodes; j++) {
if(postorder[j] == inorder[i] && j > highestIndex) {
highestIndex = j;
splitAt = i;
break;
}
}
}
// case when input is invalid tree
if(!highestIndex) {
fprintf(out, "Tree cannot be formed\n");
exit(0);
}
// insert data into node and get left and right subtree
root -> data = inorder[splitAt];
root -> left = tree(start, splitAt - 1, nodes, inorder, postorder, out);
root -> right = tree(splitAt + 1, end, nodes, inorder, postorder, out);
return root;
}
void preorder(nodeptr head, FILE* out) {
if(head == NULL)
return;
fprintf(out, "%c ", head->data);
preorder(head->left, out);
preorder(head->right, out);
}
int main(void) {
// store inorder and postorder
char inorder[1000], postorder[1000];
// number of nodes
int nodes = 0;
// temporary char storage variable
char c;
FILE *input = fopen("ipseq.txt", "r");
if(input == NULL) {
printf("ipseq can't be opened\n");
return 0;
}
FILE *output = fopen("1601CS43.txt", "w");
// get inorder
while(1) {
if(fscanf(input, "%c", &c) == EOF || c == '\n') break;
if(c == ' ') continue;
inorder[++nodes] = c;
}
// if first line has no nodes
if(!nodes) {
printf("invalid input file\n");
return 0;
}
// tmp for checking whether inorder and postorder have same number of nodes
int tmpNodeCount = 0;
while(1) {
if(fscanf(input, "%c", &c) == EOF || c == '\n') break;
if(c == ' ') continue;
postorder[++tmpNodeCount] = c;
}
if(tmpNodeCount != nodes) {
printf("Invalid input file\n");
return 0;
}
// get preorder
nodeptr head = tree(1, nodes, nodes, inorder, postorder, output);
fprintf(output, "The preorder sequence is: ");
preorder(head, output);
fprintf(output, "\n");
// close files
fclose(input);
fclose(output);
}