-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path3.traversal.py
160 lines (119 loc) · 3.83 KB
/
3.traversal.py
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
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.__root = None
def insert(self, value): # Big-O: O(n) / Big-Theta: Θ(log n)
if self.__root is None:
self.__root = Node(value)
else:
self.__insert(self.__root, value)
def __insert(self, node, value):
if value < node.value:
if node.left is None:
node.left = Node(value)
else:
self.__insert(node.left, value)
else:
if node.right is None:
node.right = Node(value)
else:
self.__insert(node.right, value)
def delete(self, target): # Big-O: O(n) / Big-Theta: Θ(log n)
self.__root = self.__delete(self.__root, target)
def __delete(self, node, target):
if node is None:
return None
if target < node.value:
node.left = self.__delete(node.left, target)
elif target > node.value:
node.right = self.__delete(node.right, target)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
node.value = self.__minOfRightSubTree(node.right)
node.right = self.__delete(node.right, node.value)
return node
def __minOfRightSubTree(self, node):
current = node
while current.left is not None:
current = current.left
return current.value
def print_tree(self):
self.__print_tree(self.__root, "", True)
def __print_tree(self, node, indent, last):
if node is not None:
print(indent, end='')
if last:
print("R -> ", end='')
indent += " "
else:
print("L -> ", end='')
indent += "| "
print(node.value)
self.__print_tree(node.left, indent, False)
self.__print_tree(node.right, indent, True)
def inorder(self):
return self.__inorder(self.__root)
def __inorder(self, node):
values = []
if node is not None:
values = self.__inorder(node.left)
values.append(node.value)
values = values + self.__inorder(node.right)
return values
def preorder(self):
return self.__preorder(self.__root)
def __preorder(self, node):
values = []
if node is not None:
values.append(node.value)
values = values + self.__preorder(node.left)
values = values + self.__preorder(node.right)
return values
def postorder(self):
return self.__postorder(self.__root)
def __postorder(self, node):
values = []
if node is not None:
values = self.__postorder(node.left)
values = values + self.__postorder(node.right)
values.append(node.value)
return values
bst = BinarySearchTree()
bst.insert(50)
bst.insert(90)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(10)
bst.insert(60)
bst.insert(80)
bst.print_tree()
print(f'Inorder : {bst.inorder()}')
print(f'Preorder : {bst.preorder()}')
print(f'Postorder: {bst.postorder()}')
print("\nDelete 20:")
bst.delete(20)
bst.print_tree()
print(f'Inorder : {bst.inorder()}')
print(f'Preorder : {bst.preorder()}')
print(f'Postorder: {bst.postorder()}')
print("\nDelete 70:")
bst.delete(70)
bst.print_tree()
print(f'Inorder : {bst.inorder()}')
print(f'Preorder : {bst.preorder()}')
print(f'Postorder: {bst.postorder()}')
print("\nDelete 50:")
bst.delete(50)
bst.print_tree()
print(f'Inorder : {bst.inorder()}')
print(f'Preorder : {bst.preorder()}')
print(f'Postorder: {bst.postorder()}')