master
1#include "binary_tree.h"
2#include <cgreen/cgreen.h>
3#include <string.h>
4
5int visited[32];
6Node *nodes[32];
7int visited_count;
8
9Describe(BinaryTree);
10BeforeEach(BinaryTree) {
11 memset(visited, 0, sizeof(visited));
12 memset(nodes, 0, sizeof(nodes));
13 visited_count = 0;
14}
15AfterEach(BinaryTree) {}
16
17void visitor(Node *node) {
18 visited[visited_count] = node->data;
19 nodes[visited_count] = node;
20 visited_count++;
21}
22
23Node *next(Node *self, Node *x, enum Traversal traversal) {
24 traverse(self, visitor, traversal);
25
26 for (int i = 0; i < visited_count; i++)
27 if (nodes[i] == x)
28 return nodes[i + 1];
29 return NULL;
30}
31
32Node *preorder_next(Node *self, Node *x) { return next(self, x, PREORDER); }
33
34Node *inorder_next(Node *self, Node *x) { return next(self, x, INORDER); }
35
36Node *postorder_next(Node *self, Node *x) { return next(self, x, POSTORDER); }
37
38Ensure(BinaryTree, when_traversing_in_preorder_when_the_tree_is_empty) {
39 traverse(NULL, visitor, PREORDER);
40
41 assert_that(visited_count, is_equal_to(0));
42}
43
44Ensure(BinaryTree,
45 when_traversing_in_preorder_when_the_tree_has_a_single_node) {
46 Node *node = initialize(100);
47
48 traverse(node, visitor, PREORDER);
49
50 assert_that(visited_count, is_equal_to(1));
51 assert_that(visited[0], is_equal_to(100));
52 destroy(node);
53}
54
55Ensure(BinaryTree, when_traversing_in_preorder_when_the_tree_has_a_left_node) {
56 Node *node = initialize(100);
57 node->left = initialize(200);
58
59 traverse(node, visitor, PREORDER);
60
61 assert_that(visited_count, is_equal_to(2));
62 assert_that(visited[0], is_equal_to(100));
63 assert_that(visited[1], is_equal_to(200));
64 destroy(node);
65}
66
67Ensure(BinaryTree, when_traversing_in_preorder_when_the_tree_has_a_right_node) {
68 Node *node = initialize(100);
69 node->right = initialize(300);
70
71 traverse(node, visitor, PREORDER);
72
73 assert_that(visited_count, is_equal_to(2));
74 assert_that(visited[0], is_equal_to(100));
75 assert_that(visited[1], is_equal_to(300));
76 destroy(node);
77}
78
79Ensure(BinaryTree,
80 when_traversing_in_preorder_when_the_tree_has_a_left_and_right_node) {
81 Node *node = initialize(100);
82 node->left = initialize(200);
83 node->right = initialize(300);
84
85 traverse(node, visitor, PREORDER);
86
87 assert_that(visited_count, is_equal_to(3));
88 assert_that(visited[0], is_equal_to(100));
89 assert_that(visited[1], is_equal_to(200));
90 assert_that(visited[2], is_equal_to(300));
91 destroy(node);
92}
93
94Ensure(BinaryTree,
95 when_traversing_in_preorder_when_the_tree_has_multiple_levels) {
96 Node *node = initialize(100);
97 node->left = initialize(200);
98 node->right = initialize(300);
99
100 node->left->left = initialize(400);
101 node->left->right = initialize(500);
102
103 traverse(node, visitor, PREORDER);
104
105 assert_that(visited_count, is_equal_to(5));
106 assert_that(visited[0], is_equal_to(100));
107 assert_that(visited[1], is_equal_to(200));
108 assert_that(visited[2], is_equal_to(400));
109 assert_that(visited[3], is_equal_to(500));
110 assert_that(visited[4], is_equal_to(300));
111 destroy(node);
112}
113
114Ensure(BinaryTree, when_traversing_in_postorder_when_the_tree_is_empty) {
115 traverse(NULL, visitor, POSTORDER);
116
117 assert_that(visited_count, is_equal_to(0));
118}
119
120Ensure(BinaryTree,
121 when_traversing_in_postorder_when_the_tree_has_a_single_node) {
122 Node *node = initialize(100);
123
124 traverse(node, visitor, POSTORDER);
125
126 assert_that(visited_count, is_equal_to(1));
127 assert_that(visited[0], is_equal_to(100));
128 destroy(node);
129}
130
131Ensure(BinaryTree, when_traversing_in_postorder_when_the_tree_has_a_left_node) {
132 Node *node = initialize(100);
133 node->left = initialize(200);
134
135 traverse(node, visitor, POSTORDER);
136
137 assert_that(visited_count, is_equal_to(2));
138 assert_that(visited[0], is_equal_to(200));
139 assert_that(visited[1], is_equal_to(100));
140 destroy(node);
141}
142
143Ensure(BinaryTree,
144 when_traversing_in_postorder_when_the_tree_has_a_right_node) {
145 Node *node = initialize(100);
146 node->right = initialize(300);
147
148 traverse(node, visitor, POSTORDER);
149
150 assert_that(visited_count, is_equal_to(2));
151 assert_that(visited[0], is_equal_to(300));
152 assert_that(visited[1], is_equal_to(100));
153 destroy(node);
154}
155
156Ensure(BinaryTree,
157 when_traversing_in_postorder_when_the_tree_has_a_left_and_right_node) {
158 Node *node = initialize(100);
159 node->left = initialize(200);
160 node->right = initialize(300);
161
162 traverse(node, visitor, POSTORDER);
163
164 assert_that(visited_count, is_equal_to(3));
165 assert_that(visited[0], is_equal_to(200));
166 assert_that(visited[1], is_equal_to(300));
167 assert_that(visited[2], is_equal_to(100));
168 destroy(node);
169}
170
171Ensure(BinaryTree,
172 when_traversing_in_postorder_when_the_tree_has_multiple_levels) {
173 Node *node = initialize(100);
174 node->left = initialize(200);
175 node->right = initialize(300);
176
177 node->left->left = initialize(400);
178 node->left->right = initialize(500);
179
180 traverse(node, visitor, POSTORDER);
181
182 assert_that(visited_count, is_equal_to(5));
183 assert_that(visited[0], is_equal_to(400));
184 assert_that(visited[1], is_equal_to(500));
185 assert_that(visited[2], is_equal_to(200));
186 assert_that(visited[3], is_equal_to(300));
187 assert_that(visited[4], is_equal_to(100));
188 destroy(node);
189}
190
191Ensure(BinaryTree, when_traversing_inorder_when_the_tree_is_empty) {
192 traverse(NULL, visitor, INORDER);
193
194 assert_that(visited_count, is_equal_to(0));
195}
196
197Ensure(BinaryTree, when_traversing_inorder_when_the_tree_has_a_single_node) {
198 Node *node = initialize(100);
199
200 traverse(node, visitor, INORDER);
201
202 assert_that(visited_count, is_equal_to(1));
203 assert_that(visited[0], is_equal_to(100));
204 destroy(node);
205}
206
207Ensure(BinaryTree, when_traversing_inorder_when_the_tree_has_a_left_node) {
208 Node *node = initialize(100);
209 node->left = initialize(200);
210
211 traverse(node, visitor, INORDER);
212
213 assert_that(visited_count, is_equal_to(2));
214 assert_that(visited[0], is_equal_to(200));
215 assert_that(visited[1], is_equal_to(100));
216 destroy(node);
217}
218
219Ensure(BinaryTree, when_traversing_inorder_when_the_tree_has_a_right_node) {
220 Node *node = initialize(100);
221 node->right = initialize(300);
222
223 traverse(node, visitor, INORDER);
224
225 assert_that(visited_count, is_equal_to(2));
226 assert_that(visited[0], is_equal_to(100));
227 assert_that(visited[1], is_equal_to(300));
228 destroy(node);
229}
230
231Ensure(BinaryTree,
232 when_traversing_inorder_when_the_tree_has_a_left_and_right_node) {
233 Node *node = initialize(100);
234 node->left = initialize(200);
235 node->right = initialize(300);
236
237 traverse(node, visitor, INORDER);
238
239 assert_that(visited_count, is_equal_to(3));
240 assert_that(visited[0], is_equal_to(200));
241 assert_that(visited[1], is_equal_to(100));
242 assert_that(visited[2], is_equal_to(300));
243 destroy(node);
244}
245
246Ensure(BinaryTree, when_traversing_inorder_when_the_tree_has_multiple_levels) {
247 Node *node = initialize(100);
248 node->left = initialize(200);
249 node->right = initialize(300);
250
251 node->left->left = initialize(400);
252 node->left->right = initialize(500);
253
254 traverse(node, visitor, INORDER);
255
256 assert_that(visited_count, is_equal_to(5));
257 assert_that(visited[0], is_equal_to(400));
258 assert_that(visited[1], is_equal_to(200));
259 assert_that(visited[2], is_equal_to(500));
260 assert_that(visited[3], is_equal_to(100));
261 assert_that(visited[4], is_equal_to(300));
262 destroy(node);
263}
264
265Ensure(BinaryTree, when_finding_the_next_node_in_a_preorder_traversal) {
266 Node *a = initialize(100);
267 Node *b = initialize(200);
268 Node *c = initialize(300);
269 Node *d = initialize(400);
270 Node *e = initialize(500);
271
272 a->left = b;
273 a->right = c;
274 b->left = d;
275 b->right = e;
276
277 assert_that(preorder_next(a, a), is_equal_to(b));
278 assert_that(preorder_next(a, b), is_equal_to(d));
279 assert_that(preorder_next(a, c), is_equal_to(a));
280 assert_that(preorder_next(a, d), is_equal_to(e));
281 assert_that(preorder_next(a, e), is_equal_to(c));
282
283 destroy(a);
284}
285
286Ensure(BinaryTree, when_finding_the_next_node_in_a_inorder_traversal) {
287 Node *a = initialize(100);
288 Node *b = initialize(200);
289 Node *c = initialize(300);
290 Node *d = initialize(400);
291 Node *e = initialize(500);
292
293 a->left = b;
294 a->right = c;
295 b->left = d;
296 b->right = e;
297
298 assert_that(inorder_next(a, a), is_equal_to(c));
299 assert_that(inorder_next(a, b), is_equal_to(e));
300 assert_that(inorder_next(a, c), is_equal_to(d));
301 assert_that(inorder_next(a, d), is_equal_to(b));
302 assert_that(inorder_next(a, e), is_equal_to(a));
303
304 destroy(a);
305}
306
307Ensure(BinaryTree, when_finding_the_next_node_in_a_postorder_traversal) {
308 Node *a = initialize(100);
309 Node *b = initialize(200);
310 Node *c = initialize(300);
311 Node *d = initialize(400);
312 Node *e = initialize(500);
313
314 a->left = b;
315 a->right = c;
316 b->left = d;
317 b->right = e;
318
319 assert_that(postorder_next(a, a), is_equal_to(NULL));
320 assert_that(postorder_next(a, b), is_equal_to(c));
321 assert_that(postorder_next(a, c), is_equal_to(a));
322 assert_that(postorder_next(a, d), is_equal_to(e));
323 assert_that(postorder_next(a, e), is_equal_to(b));
324
325 destroy(a);
326}
327
328TestSuite *binary_tree_tests() {
329 TestSuite *suite = create_test_suite();
330
331 add_test_with_context(suite, BinaryTree,
332 when_traversing_in_preorder_when_the_tree_is_empty);
333 add_test_with_context(
334 suite, BinaryTree,
335 when_traversing_in_preorder_when_the_tree_has_a_single_node);
336 add_test_with_context(
337 suite, BinaryTree,
338 when_traversing_in_preorder_when_the_tree_has_a_left_node);
339 add_test_with_context(
340 suite, BinaryTree,
341 when_traversing_in_preorder_when_the_tree_has_a_right_node);
342 add_test_with_context(
343 suite, BinaryTree,
344 when_traversing_in_preorder_when_the_tree_has_a_left_and_right_node);
345 add_test_with_context(
346 suite, BinaryTree,
347 when_traversing_in_preorder_when_the_tree_has_multiple_levels);
348
349 add_test_with_context(suite, BinaryTree,
350 when_traversing_in_postorder_when_the_tree_is_empty);
351 add_test_with_context(
352 suite, BinaryTree,
353 when_traversing_in_postorder_when_the_tree_has_a_single_node);
354 add_test_with_context(
355 suite, BinaryTree,
356 when_traversing_in_postorder_when_the_tree_has_a_left_node);
357 add_test_with_context(
358 suite, BinaryTree,
359 when_traversing_in_postorder_when_the_tree_has_a_right_node);
360 add_test_with_context(
361 suite, BinaryTree,
362 when_traversing_in_postorder_when_the_tree_has_a_left_and_right_node);
363 add_test_with_context(
364 suite, BinaryTree,
365 when_traversing_in_postorder_when_the_tree_has_multiple_levels);
366
367 add_test_with_context(suite, BinaryTree,
368 when_traversing_inorder_when_the_tree_is_empty);
369 add_test_with_context(
370 suite, BinaryTree,
371 when_traversing_inorder_when_the_tree_has_a_single_node);
372 add_test_with_context(suite, BinaryTree,
373 when_traversing_inorder_when_the_tree_has_a_left_node);
374 add_test_with_context(suite, BinaryTree,
375 when_traversing_inorder_when_the_tree_has_a_right_node);
376 add_test_with_context(
377 suite, BinaryTree,
378 when_traversing_inorder_when_the_tree_has_a_left_and_right_node);
379 add_test_with_context(
380 suite, BinaryTree,
381 when_traversing_inorder_when_the_tree_has_multiple_levels);
382
383 add_test_with_context(suite, BinaryTree,
384 when_finding_the_next_node_in_a_preorder_traversal);
385 add_test_with_context(suite, BinaryTree,
386 when_finding_the_next_node_in_a_inorder_traversal);
387 add_test_with_context(suite, BinaryTree,
388 when_finding_the_next_node_in_a_postorder_traversal);
389
390 return suite;
391}
392
393int main(int argc, char **argv) {
394 TestSuite *suite = create_test_suite();
395 add_suite(suite, binary_tree_tests());
396 return run_test_suite(suite, create_text_reporter());
397}