/home/toolbox/public_html/solutions/5/536/judged.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4
5 /*
6 * Author: Matthew Eastman <meastman@cct.lsu.edu>
7 * Date: 2006-09-26
8 * Purpose: Contest practice
9 * Problem: 536 - Tree Recovery <http://isaac.lsu.edu/udv/v5/536.html>
10 */
11
12 #define FALSE 0
13 #define TRUE 1
14
15 char inorder[30];
16 char preorder[30];
17
18 typedef struct tree_node_s
19 {
20 int data;
21 struct tree_node_s *left;
22 struct tree_node_s *right;
23 }
24 tree_node_t;
25
26 tree_node_t *createNode(int data)
27 {
28 tree_node_t *node;
29
30 node = malloc(sizeof(tree_node_t));
31 node->data = data;
32 node->left = NULL;
33 node->right = NULL;
34
35 return node;
36 }
37
38 void addChild(tree_node_t *node, int data)
39 {
40 if (data < node->data)
41 {
42 if (node->left)
43 addChild(node->left, data);
44 else
45 node->left = createNode(data);
46 }
47 else
48 {
49 if (node->right)
50 addChild(node->right, data);
51 else
52 node->right = createNode(data);
53 }
54 }
55
56 void parseTree(tree_node_t *node)
57 {
58 if (node->left)
59 parseTree(node->left);
60 if (node->right)
61 parseTree(node->right);
62 printf("%c", inorder[node->data]);
63 }
64
65 void deleteSubtree(tree_node_t *node)
66 {
67 if (node->left)
68 deleteSubtree(node->left);
69 if (node->right)
70 deleteSubtree(node->right);
71 free(node);
72 }
73
74 int getInput()
75 {
76 int keepGoing = FALSE;
77
78 if (2 == scanf(" %s %s ", preorder, inorder))
79 keepGoing = TRUE;
80
81 return keepGoing;
82 }
83
84 void solveProblem()
85 {
86 tree_node_t *tree;
87 int i;
88
89 tree = createNode(strchr(inorder, preorder[0]) - inorder);
90 for (i = 1; preorder[i]; i++)
91 {
92 addChild(tree, strchr(inorder, preorder[i]) - inorder);
93 }
94
95 parseTree(tree);
96 printf("\n");
97
98 deleteSubtree(tree);
99 }
100
101 int main()
102 {
103 while (getInput())
104 {
105 solveProblem();
106 }
107
108 return EXIT_SUCCESS;
109 }
110
111