Skip to content

Commit 89ecbd7

Browse files
laurentlucelaurentluce
committed
Improve unit tests.
1 parent b6d8373 commit 89ecbd7

File tree

1 file changed

+155
-76
lines changed

1 file changed

+155
-76
lines changed

‎algorithms/tests/test_binary_tree.py

+155-76
Original file line numberDiff line numberDiff line change
@@ -1,84 +1,163 @@
1+
import copy
12
import unittest
23
import algorithms.binary_tree as binary_tree
34

45
class BinaryTreeTest(unittest.TestCase):
5-
6-
def test_binary_tree(self):
7-
8-
data = [10, 5, 15, 4, 7, 13, 17, 11, 14]
9-
# create 2 trees with the same content
10-
root = binary_tree.Node(data[0])
11-
for i in data[1:]:
12-
root.insert(i)
13-
14-
root2 = binary_tree.Node(data[0])
15-
for i in data[1:]:
16-
root2.insert(i)
17-
18-
# check if both trees are identical
19-
self.assertTrue(root.compare_trees(root2))
20-
21-
# check the content of the tree inorder
22-
t = []
23-
for d in root.tree_data():
24-
t.append(d)
25-
self.assertEquals(t, [4, 5, 7, 10, 11, 13, 14, 15, 17])
26-
27-
# test lookup
28-
node, parent = root.lookup(9)
29-
self.assertTrue(node is None)
30-
# check if returned node and parent are correct
31-
node, parent = root.lookup(11)
32-
self.assertTrue(node.data == 11)
33-
self.assertTrue(parent.data == 13)
34-
35-
# delete a leaf node
36-
root.delete(4)
37-
# check the content of the tree inorder
38-
t = []
39-
for d in root.tree_data():
40-
t.append(d)
41-
self.assertEquals(t, [5, 7, 10, 11, 13, 14, 15, 17])
42-
43-
# delete a node with 1 child
44-
root.delete(5)
45-
# check the content of the tree inorder
46-
t = []
47-
for d in root.tree_data():
48-
t.append(d)
49-
self.assertEquals(t, [7, 10, 11, 13, 14, 15, 17])
50-
51-
# delete a node with 2 children
52-
root.delete(13)
53-
# check the content of the tree inorder
54-
t = []
55-
for d in root.tree_data():
56-
t.append(d)
57-
self.assertEquals(t, [7, 10, 11, 14, 15, 17])
58-
59-
# delete a node with 2 children
60-
root.delete(15)
61-
# check the content of the tree inorder
62-
t = []
63-
for d in root.tree_data():
64-
t.append(d)
65-
self.assertEquals(t, [7, 10, 11, 14, 17])
66-
67-
# check for root deletion
68-
root = binary_tree.Node(1)
69-
root.insert(2)
70-
root.insert(0)
71-
root.delete(1)
72-
self.assertEquals(root.data, 2)
73-
root.delete(2)
74-
self.assertEquals(root.data, 0)
75-
root.delete(0)
76-
self.assertEquals(root.data, None)
77-
root.insert(1)
78-
self.assertEquals(root.data, 1)
79-
self.assertEquals(root.left, None)
80-
self.assertEquals(root.right, None)
816

7+
def setUp(self):
8+
self.root_single_node = binary_tree.Node(None)
9+
self.root = binary_tree.Node(10)
10+
self.root.left = binary_tree.Node(5)
11+
self.root.left.left = binary_tree.Node(3)
12+
self.root.left.right = binary_tree.Node(7)
13+
self.root.right = binary_tree.Node(15)
14+
self.root.right.left = binary_tree.Node(12)
15+
self.root.right.left.left = binary_tree.Node(11)
16+
self.root.right.right = binary_tree.Node(20)
17+
self.root_copy = copy.deepcopy(self.root)
18+
19+
def test_insert(self):
20+
root = self.root_single_node
21+
22+
root.insert(10)
23+
self.assertEqual(root.data, 10)
24+
25+
root.insert(5)
26+
self.assertEqual(root.left.data, 5)
27+
28+
root.insert(15)
29+
self.assertEqual(root.right.data, 15)
30+
31+
root.insert(8)
32+
self.assertEqual(root.left.right.data, 8)
33+
34+
root.insert(2)
35+
self.assertEqual(root.left.left.data, 2)
36+
37+
root.insert(12)
38+
self.assertEqual(root.right.left.data, 12)
39+
40+
root.insert(17)
41+
self.assertEqual(root.right.right.data, 17)
42+
43+
def test_lookup(self):
44+
node, parent = self.root.lookup(0)
45+
self.assertIsNone(parent)
46+
self.assertIsNone(node)
47+
48+
node, parent = self.root.lookup(13)
49+
self.assertIsNone(parent)
50+
self.assertIsNone(node)
51+
52+
node, parent = self.root.lookup(7)
53+
self.assertIs(node, self.root.left.right)
54+
self.assertIs(parent, self.root.left)
55+
56+
def test_delete_root_no_child(self):
57+
self.root_single_node.data = 7
58+
self.root_single_node.delete(7)
59+
self.assertIsNone(self.root_single_node.data)
60+
61+
def test_delete_root_one_child(self):
62+
self.root_single_node.data = 7
63+
self.root_single_node.insert(3)
64+
self.root_single_node.delete(7)
65+
self.assertEqual(self.root_single_node.data, 3)
66+
67+
def test_delete_one_child_left(self):
68+
self.root.delete(12)
69+
self.assertEqual(self.root.left.data, 5)
70+
self.assertEqual(self.root.left.left.data, 3)
71+
self.assertEqual(self.root.left.right.data, 7)
72+
self.assertEqual(self.root.right.data, 15)
73+
self.assertEqual(self.root.right.left.data, 11)
74+
self.assertEqual(self.root.right.right.data, 20)
75+
76+
def test_delete_one_child_right(self):
77+
self.root.insert(25)
78+
self.root.delete(20)
79+
self.assertEqual(self.root.left.data, 5)
80+
self.assertEqual(self.root.left.left.data, 3)
81+
self.assertEqual(self.root.left.right.data, 7)
82+
self.assertEqual(self.root.right.data, 15)
83+
self.assertEqual(self.root.right.left.data, 12)
84+
self.assertEqual(self.root.right.left.left.data, 11)
85+
self.assertEqual(self.root.right.right.data, 25)
86+
87+
def test_delete_right_leaf(self):
88+
self.root.delete(7)
89+
self.assertIsNone(self.root.left.right)
90+
self.assertEqual(self.root.left.data, 5)
91+
self.assertEqual(self.root.left.left.data, 3)
92+
self.assertEqual(self.root.right.data, 15)
93+
self.assertEqual(self.root.right.left.data, 12)
94+
self.assertEqual(self.root.right.left.left.data, 11)
95+
self.assertEqual(self.root.right.right.data, 20)
96+
97+
def test_delete_left_leaf(self):
98+
self.root.delete(3)
99+
self.assertIsNone(self.root.left.left)
100+
self.assertEqual(self.root.left.data, 5)
101+
self.assertEqual(self.root.left.right.data, 7)
102+
self.assertEqual(self.root.right.data, 15)
103+
self.assertEqual(self.root.right.left.data, 12)
104+
self.assertEqual(self.root.right.left.left.data, 11)
105+
self.assertEqual(self.root.right.right.data, 20)
106+
107+
def test_delete_right_node_two_childs(self):
108+
self.root.delete(15)
109+
self.assertEqual(self.root.left.data, 5)
110+
self.assertEqual(self.root.left.left.data, 3)
111+
self.assertEqual(self.root.left.right.data, 7)
112+
self.assertEqual(self.root.right.data, 20)
113+
self.assertEqual(self.root.right.left.data, 12)
114+
self.assertEqual(self.root.right.left.left.data, 11)
115+
116+
def test_delete_left_node_two_childs(self):
117+
self.root.delete(5)
118+
self.assertEqual(self.root.left.data, 7)
119+
self.assertEqual(self.root.left.left.data, 3)
120+
self.assertEqual(self.root.right.data, 15)
121+
self.assertEqual(self.root.right.left.data, 12)
122+
self.assertEqual(self.root.right.left.left.data, 11)
123+
self.assertEqual(self.root.right.right.data, 20)
124+
125+
def test_delete_root_two_childs(self):
126+
self.root.delete(10)
127+
self.assertEqual(self.root.left.data, 5)
128+
self.assertEqual(self.root.left.left.data, 3)
129+
self.assertEqual(self.root.left.right.data, 7)
130+
self.assertEqual(self.root.data, 11)
131+
self.assertEqual(self.root.right.data, 15)
132+
self.assertEqual(self.root.right.left.data, 12)
133+
self.assertEqual(self.root.right.right.data, 20)
134+
135+
def test_compare_trees_left_leaf_missing(self):
136+
self.root_copy.delete(11)
137+
self.assertFalse(self.root.compare_trees(self.root_copy))
138+
139+
def test_compare_trees_right_leaf_missing(self):
140+
self.root_copy.delete(20)
141+
self.assertFalse(self.root.compare_trees(self.root_copy))
142+
143+
def test_compare_trees_diff_value(self):
144+
self.root_copy.left.data = 16
145+
self.assertFalse(self.root.compare_trees(self.root_copy))
146+
147+
def test_compare_trees_extra_right_leaf(self):
148+
self.root_copy.insert(25)
149+
self.assertFalse(self.root.compare_trees(self.root_copy))
150+
151+
def test_compare_trees_extra_left_leaf(self):
152+
self.root_copy.insert(18)
153+
self.assertFalse(self.root.compare_trees(self.root_copy))
154+
155+
def test_print_tree(self):
156+
self.root.print_tree()
157+
158+
def test_tree_data(self):
159+
self.assertEqual([e for e in self.root.tree_data()],
160+
[3, 5, 7, 10, 11, 12, 15, 20])
82161

83162
if __name__ == '__main__':
84163
unittest.main()

0 commit comments

Comments
 (0)