forked from yshshrm/Algorithms-And-Data-Structures
-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathBinarySearchTree.py
More file actions
105 lines (76 loc) · 2.23 KB
/
Copy pathBinarySearchTree.py
File metadata and controls
105 lines (76 loc) · 2.23 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
class Node:
def __init__(self, label):
self.label = label
self.left = None
self.right = None
def getLabel(self):
return self.label
def setLabel(self, label):
self.label = label
def getLeft(self):
return self.left
def setLeft(self, left):
self.left = left
def getRight(self):
return self.right
def setRight(self, right):
self.right = right
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, label):
# Create a new Node
node = Node(label)
if self.empty():
self.root = node
else:
parent_node = None
cur_node = self.root
while True:
if cur_node is not None:
parent_node = cur_node
if node.getLabel() < cur_node.getLabel():
cur_node = cur_node.getLeft()
else:
cur_node = cur_node.getRight()
else:
if node.getLabel() < parent_node.getLabel():
parent_node.setLeft(node)
else:
parent_node.setRight(node)
break
def empty(self):
if self.root is None:
return True
return False
def preOrder(self, cur_node):
if cur_node is not None:
print(cur_node.getLabel(), end=" ")
self.preOrder(cur_node.getLeft())
self.preOrder(cur_node.getRight())
def postOrder(self, cur_node):
if cur_node is not None:
self.postOrder(cur_node.getLeft())
self.postOrder(cur_node.getRight())
print(cur_node.getLabel(), end=" ")
def inOrder(self, cur_node):
if cur_node is not None:
self.inOrder(cur_node.getLeft())
print(cur_node.getLabel(), end =" ")
self.inOrder(cur_node.getRight())
def getRoot(self):
return self.root
t = BinarySearchTree()
t.insert(4)
t.insert(2)
t.insert(1)
t.insert(3)
t.insert(6)
t.insert(5)
t.insert(7)
t.preOrder(t.getRoot())
print("\n")
t.inOrder(t.getRoot())
print("\n")
t.postOrder(t.getRoot())
print("\n")