forked from laurentluce/python-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathtest_binary_tree.py
More file actions
165 lines (133 loc) · 5.88 KB
/
Copy pathtest_binary_tree.py
File metadata and controls
165 lines (133 loc) · 5.88 KB
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
import copy
import unittest
import algorithms.binary_tree as binary_tree
class BinaryTreeTest(unittest.TestCase):
def setUp(self):
self.root_single_node = binary_tree.Node(None)
self.root = binary_tree.Node(10)
self.root.left = binary_tree.Node(5)
self.root.left.left = binary_tree.Node(3)
self.root.left.right = binary_tree.Node(7)
self.root.right = binary_tree.Node(15)
self.root.right.left = binary_tree.Node(12)
self.root.right.left.left = binary_tree.Node(11)
self.root.right.right = binary_tree.Node(20)
self.root_copy = copy.deepcopy(self.root)
def test_insert(self):
root = self.root_single_node
root.insert(10)
self.assertEqual(root.data, 10)
root.insert(5)
self.assertEqual(root.left.data, 5)
root.insert(15)
self.assertEqual(root.right.data, 15)
root.insert(8)
self.assertEqual(root.left.right.data, 8)
root.insert(2)
self.assertEqual(root.left.left.data, 2)
root.insert(12)
self.assertEqual(root.right.left.data, 12)
root.insert(17)
self.assertEqual(root.right.right.data, 17)
def test_lookup(self):
node, parent = self.root.lookup(0)
self.assertIsNone(parent)
self.assertIsNone(node)
node, parent = self.root.lookup(13)
self.assertIsNone(parent)
self.assertIsNone(node)
node, parent = self.root.lookup(7)
self.assertIs(node, self.root.left.right)
self.assertIs(parent, self.root.left)
def test_delete_root_no_child(self):
self.root_single_node.data = 7
self.root_single_node.delete(7)
self.assertIsNone(self.root_single_node.data)
def test_delete_root_one_child(self):
self.root_single_node.data = 7
self.root_single_node.insert(3)
self.root_single_node.delete(7)
self.assertEqual(self.root_single_node.data, 3)
def test_delete_one_child_left(self):
self.root.delete(12)
self.assertEqual(self.root.left.data, 5)
self.assertEqual(self.root.left.left.data, 3)
self.assertEqual(self.root.left.right.data, 7)
self.assertEqual(self.root.right.data, 15)
self.assertEqual(self.root.right.left.data, 11)
self.assertEqual(self.root.right.right.data, 20)
def test_delete_one_child_right(self):
self.root.insert(25)
self.root.delete(20)
self.assertEqual(self.root.left.data, 5)
self.assertEqual(self.root.left.left.data, 3)
self.assertEqual(self.root.left.right.data, 7)
self.assertEqual(self.root.right.data, 15)
self.assertEqual(self.root.right.left.data, 12)
self.assertEqual(self.root.right.left.left.data, 11)
self.assertEqual(self.root.right.right.data, 25)
def test_delete_right_leaf(self):
self.root.delete(7)
self.assertIsNone(self.root.left.right)
self.assertEqual(self.root.left.data, 5)
self.assertEqual(self.root.left.left.data, 3)
self.assertEqual(self.root.right.data, 15)
self.assertEqual(self.root.right.left.data, 12)
self.assertEqual(self.root.right.left.left.data, 11)
self.assertEqual(self.root.right.right.data, 20)
def test_delete_left_leaf(self):
self.root.delete(3)
self.assertIsNone(self.root.left.left)
self.assertEqual(self.root.left.data, 5)
self.assertEqual(self.root.left.right.data, 7)
self.assertEqual(self.root.right.data, 15)
self.assertEqual(self.root.right.left.data, 12)
self.assertEqual(self.root.right.left.left.data, 11)
self.assertEqual(self.root.right.right.data, 20)
def test_delete_right_node_two_childs(self):
self.root.delete(15)
self.assertEqual(self.root.left.data, 5)
self.assertEqual(self.root.left.left.data, 3)
self.assertEqual(self.root.left.right.data, 7)
self.assertEqual(self.root.right.data, 20)
self.assertEqual(self.root.right.left.data, 12)
self.assertEqual(self.root.right.left.left.data, 11)
def test_delete_left_node_two_childs(self):
self.root.delete(5)
self.assertEqual(self.root.left.data, 7)
self.assertEqual(self.root.left.left.data, 3)
self.assertEqual(self.root.right.data, 15)
self.assertEqual(self.root.right.left.data, 12)
self.assertEqual(self.root.right.left.left.data, 11)
self.assertEqual(self.root.right.right.data, 20)
def test_delete_root_two_childs(self):
self.root.delete(10)
self.assertEqual(self.root.left.data, 5)
self.assertEqual(self.root.left.left.data, 3)
self.assertEqual(self.root.left.right.data, 7)
self.assertEqual(self.root.data, 11)
self.assertEqual(self.root.right.data, 15)
self.assertEqual(self.root.right.left.data, 12)
self.assertEqual(self.root.right.right.data, 20)
def test_compare_trees_left_leaf_missing(self):
self.root_copy.delete(11)
self.assertFalse(self.root.compare_trees(self.root_copy))
def test_compare_trees_right_leaf_missing(self):
self.root_copy.delete(20)
self.assertFalse(self.root.compare_trees(self.root_copy))
def test_compare_trees_diff_value(self):
self.root_copy.left.data = 16
self.assertFalse(self.root.compare_trees(self.root_copy))
def test_compare_trees_extra_right_leaf(self):
self.root_copy.insert(25)
self.assertFalse(self.root.compare_trees(self.root_copy))
def test_compare_trees_extra_left_leaf(self):
self.root_copy.insert(18)
self.assertFalse(self.root.compare_trees(self.root_copy))
def test_print_tree(self):
self.root.print_tree()
def test_tree_data(self):
self.assertEqual([e for e in self.root.tree_data()],
[3, 5, 7, 10, 11, 12, 15, 20])
if __name__ == '__main__':
unittest.main()