-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary-search-tree.py
More file actions
134 lines (107 loc) · 3.57 KB
/
Copy pathbinary-search-tree.py
File metadata and controls
134 lines (107 loc) · 3.57 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
from unittest import result
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):
new_node = Node(value)
if self.root is None:
self.root = new_node
return True
temp = self.root
while(True):
if new_node.value == temp.value:
return False
if new_node.value < temp.value:
if temp.left is None:
temp.left = new_node
return True
temp = temp.left
else:
if temp.right is None:
temp.right = new_node
return True
temp = temp.right
def contains(self, value):
temp = self.root
while temp is not None:
if value == temp.value:
return True
if value < temp.value:
temp = temp.left
else:
temp = temp.right
return False
def min_value(self, current_node):
while current_node.left is not None:
current_node = current_node.left
return current_node
def BFS(self):
current_node = self.root
queue = []
results = []
queue.append(current_node)
while len(queue) > 0:
current_node = queue.pop(0)
results.append(current_node.value)
if current_node.left is not None:
queue.append(current_node.left)
if current_node.right is not None:
queue.append(current_node.right)
return results
def dfs_pre_order(self):
results = []
def traverse(current_node):
results.append(current_node.value)
if current_node.left is not None:
traverse(current_node.left)
if current_node.right is not None:
traverse(current_node.right)
traverse(self.root)
return results
def dfs_post_order(self):
results = []
def traverse(current_node):
if current_node.left is not None:
traverse(current_node.left)
if current_node.right is not None:
traverse(current_node.right)
results.append(current_node.value)
traverse(self.root)
return results
def dfs_in_order(self):
results = []
def traverse(current_node):
if current_node.left is not None:
traverse(current_node.left)
results.append(current_node.value)
if current_node.right is not None:
traverse(current_node.right)
traverse(self.root)
return results
# my_tree = BinarySearchTree()
# my_tree.insert(2)
# my_tree.insert(1)
# my_tree.insert(3)
# print(my_tree.min_value(my_tree.root).value)
# print(my_tree.contains(2))
# print(my_tree.contains(5))
# print(my_tree.root.value)
# print(my_tree.root.left.value)
# print(my_tree.root.right.value)
my_tree = BinarySearchTree()
my_tree.insert(47)
my_tree.insert(21)
my_tree.insert(76)
my_tree.insert(18)
my_tree.insert(27)
my_tree.insert(52)
my_tree.insert(82)
print(my_tree.BFS())
print(my_tree.dfs_pre_order())
print(my_tree.dfs_post_order())
print(my_tree.dfs_in_order())