-
-
Notifications
You must be signed in to change notification settings - Fork 77
/
binary_search_tree.py
99 lines (74 loc) · 2.83 KB
/
binary_search_tree.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
from queue import Queue
class Node:
def __init__(self, value):
self.value = value
self.left_child = None
self.right_child = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
if self.root:
self.insert_node(self.root, value)
else:
self.root = Node(value)
def insert_node(self, current_node, value):
if value <= current_node.value and current_node.left_child:
self.insert_node(current_node.left_child, value)
elif value <= current_node.value:
current_node.left_child = Node(value)
elif current_node.right_child:
self.insert_node(current_node.right_child, value)
else:
current_node.right_child = Node(value)
def find(self, value):
return self.find_node(self.root, value)
def find_node(self, current_node, value):
if value < current_node.value and current_node.left_child:
return self.find_node(current_node.left_child, value)
if value > current_node.value and current_node.right_child:
return self.find_node(current_node.right_child, value)
return value == current_node.value
def pre_order(self):
if self.root:
self.pre_order_traversal(self.root)
else:
print('Tree empty')
def pre_order_traversal(self, current_node):
print(current_node.value)
if current_node.left_child:
self.pre_order_traversal(current_node.left_child)
if current_node.right_child:
self.pre_order_traversal(current_node.right_child)
def in_order(self):
if self.root:
self.in_order_traversal(self.root)
else:
print('Tree empty')
def in_order_traversal(self, current_node):
if current_node.left_child:
self.in_order_traversal(current_node.left_child)
print(current_node.value)
if current_node.right_child:
self.in_order_traversal(current_node.right_child)
def post_order(self):
if self.root:
self.post_order_traversal(self.root)
else:
print('Tree empty')
def post_order_traversal(self, current_node):
if current_node.left_child:
self.post_order_traversal(current_node.left_child)
if current_node.right_child:
self.post_order_traversal(current_node.right_child)
print(current_node.value)
def bfs(self):
queue = Queue()
queue.put(self.root)
while not queue.empty():
current_node = queue.get()
print(current_node.value)
if current_node.left_child:
queue.put(current_node.left_child)
if current_node.right_child:
queue.put(current_node.right_child)