master
1#include "btree.h"
2#include <cgreen/cgreen.h>
3#include <string.h>
4
5Describe(BinaryTree);
6BeforeEach(BinaryTree) {}
7AfterEach(BinaryTree) {}
8
9Ensure(BinaryTree, when_the_tree_is_NULL) {
10 BTree *tree = btree_insert(NULL, 10);
11
12 assert_that(tree, is_not_equal_to(NULL));
13 assert_that(tree->data, is_equal_to(10));
14}
15
16Ensure(BinaryTree,
17 when_the_tree_has_a_single_node_it_returns_the_items_in_order) {
18 BTree *tree = btree_insert(NULL, 10);
19
20 btree_in_order_number(tree);
21
22 assert_that(tree->in_order[0], is_equal_to(10));
23}
24
25Ensure(BinaryTree,
26 when_the_tree_has_multiple_levels_it_returns_the_items_in_order) {
27 BTree *tree = btree_insert(NULL, 10);
28
29 btree_insert(tree, 5);
30 btree_insert(tree, 15);
31 btree_insert(tree, 7);
32 btree_insert(tree, 12);
33 btree_insert(tree, 18);
34 btree_insert(tree, 3);
35
36 btree_in_order_number(tree);
37
38 assert_that(tree->in_order[0], is_equal_to(3));
39 assert_that(tree->in_order[1], is_equal_to(5));
40 assert_that(tree->in_order[2], is_equal_to(7));
41 assert_that(tree->in_order[3], is_equal_to(10));
42 assert_that(tree->in_order[4], is_equal_to(12));
43 assert_that(tree->in_order[5], is_equal_to(15));
44 assert_that(tree->in_order[6], is_equal_to(18));
45}
46
47Ensure(BinaryTree,
48 when_the_tree_has_multiple_levels_it_returns_the_items_in_pre_order) {
49 BTree *tree = btree_insert(NULL, 10);
50
51 btree_insert(tree, 5);
52 btree_insert(tree, 15);
53 btree_insert(tree, 7);
54 btree_insert(tree, 12);
55 btree_insert(tree, 18);
56 btree_insert(tree, 3);
57 /*
58 10
59 / \
60 5 15
61 / \ / \
623 7 12 18
63 */
64
65 btree_pre_order_number(tree);
66
67 assert_that(tree->pre_order[0], is_equal_to(10));
68 assert_that(tree->pre_order[1], is_equal_to(5));
69 assert_that(tree->pre_order[2], is_equal_to(3));
70 assert_that(tree->pre_order[3], is_equal_to(7));
71 assert_that(tree->pre_order[4], is_equal_to(15));
72 assert_that(tree->pre_order[5], is_equal_to(12));
73 assert_that(tree->pre_order[6], is_equal_to(18));
74}
75
76Ensure(BinaryTree,
77 when_the_tree_has_multiple_levels_it_returns_the_items_in_post_order) {
78 BTree *tree = btree_insert(NULL, 10);
79
80 btree_insert(tree, 5);
81 btree_insert(tree, 15);
82 btree_insert(tree, 7);
83 btree_insert(tree, 12);
84 btree_insert(tree, 18);
85 btree_insert(tree, 3);
86 /*
87 10
88 / \
89 5 15
90 / \ / \
913 7 12 18
92 */
93
94 btree_post_order_number(tree);
95
96 assert_that(tree->post_order[0], is_equal_to(3));
97 assert_that(tree->post_order[1], is_equal_to(7));
98 assert_that(tree->post_order[2], is_equal_to(5));
99 assert_that(tree->post_order[3], is_equal_to(12));
100 assert_that(tree->post_order[4], is_equal_to(18));
101 assert_that(tree->post_order[5], is_equal_to(15));
102 assert_that(tree->post_order[6], is_equal_to(10));
103}
104
105Ensure(
106 BinaryTree,
107 when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side) {
108 BTree *tree = btree_init(10);
109 btree_insert(tree, -5);
110
111 assert_that(tree->left, is_not_equal_to(NULL));
112 assert_that(tree->left->data, is_equal_to(-5));
113}
114
115Ensure(
116 BinaryTree,
117 when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side) {
118 BTree *tree = btree_init(10);
119
120 btree_insert(tree, 16);
121
122 assert_that(tree->right, is_not_equal_to(NULL));
123 assert_that(tree->right->data, is_equal_to(16));
124}
125
126Ensure(
127 BinaryTree,
128 when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side) {
129 BTree *tree = btree_init(10);
130
131 btree_insert(tree, 10);
132
133 assert_that(tree->left, is_not_equal_to(NULL));
134 assert_that(tree->left->data, is_equal_to(10));
135}
136
137Ensure(
138 BinaryTree,
139 when_inserting_multiple_items_into_a_tree_it_inserts_in_the_correct_position) {
140 BTree *tree = btree_insert(NULL, 10);
141
142 btree_insert(tree, -5);
143 btree_insert(tree, 16);
144
145 assert_that(tree->data, is_equal_to(10));
146 assert_that(tree->left->data, is_equal_to(-5));
147 assert_that(tree->right->data, is_equal_to(16));
148
149 btree_insert(tree, -8);
150
151 assert_that(tree->left->left, is_not_equal_to(NULL));
152 assert_that(tree->left->left->data, is_equal_to(-8));
153
154 btree_insert(tree, 7);
155
156 assert_that(tree->left->right, is_not_equal_to(NULL));
157 assert_that(tree->left->right->data, is_equal_to(7));
158
159 btree_insert(tree, 18);
160
161 assert_that(tree->right->right, is_not_equal_to(NULL));
162 assert_that(tree->right->right->data, is_equal_to(18));
163
164 btree_insert(tree, 6);
165
166 assert_that(tree->left->right->left, is_not_equal_to(NULL));
167 assert_that(tree->left->right->left->data, is_equal_to(6));
168}
169
170Ensure(
171 BinaryTree,
172 when_inserting_items_described_in_the_assignment_it_inserts_in_the_expected_position_in_the_tree) {
173 BTree *tree = btree_insert(NULL, 1);
174 tree = btree_insert(tree, 5);
175 tree = btree_insert(tree, 2);
176 tree = btree_insert(tree, 4);
177 tree = btree_insert(tree, 3);
178
179 assert_that(tree, is_not_equal_to(NULL));
180}
181
182TestSuite *btree_tests() {
183 TestSuite *suite = create_test_suite();
184 add_test_with_context(suite, BinaryTree, when_the_tree_is_NULL);
185 add_test_with_context(
186 suite, BinaryTree,
187 when_the_tree_has_a_single_node_it_returns_the_items_in_order);
188 add_test_with_context(
189 suite, BinaryTree,
190 when_the_tree_has_multiple_levels_it_returns_the_items_in_order);
191 add_test_with_context(
192 suite, BinaryTree,
193 when_the_tree_has_multiple_levels_it_returns_the_items_in_pre_order);
194 add_test_with_context(
195 suite, BinaryTree,
196 when_the_tree_has_multiple_levels_it_returns_the_items_in_post_order);
197
198 add_test_with_context(
199 suite, BinaryTree,
200 when_inserting_an_item_less_than_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
201 add_test_with_context(
202 suite, BinaryTree,
203 when_inserting_an_item_greater_than_the_root_in_a_tree_it_creates_a_node_on_the_right_side);
204 add_test_with_context(
205 suite, BinaryTree,
206 when_inserting_an_item_equal_to_the_root_in_a_tree_it_creates_a_node_on_the_left_side);
207 add_test_with_context(
208 suite, BinaryTree,
209 when_inserting_multiple_items_into_a_tree_it_inserts_in_the_correct_position);
210 add_test_with_context(
211 suite, BinaryTree,
212 when_inserting_items_described_in_the_assignment_it_inserts_in_the_expected_position_in_the_tree);
213 return suite;
214}
215
216extern TestSuite *stack_tests();
217
218int main(int argc, char **argv) {
219 TestSuite *suite = create_test_suite();
220 add_suite(suite, btree_tests());
221 add_suite(suite, stack_tests());
222 return run_test_suite(suite, create_text_reporter());
223}