forked from OmkarPathak/Python-Programs
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathP43_BinarySearchTree.py
More file actions
145 lines (120 loc) · 3.94 KB
/
Copy pathP43_BinarySearchTree.py
File metadata and controls
145 lines (120 loc) · 3.94 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
# Author: OMKAR PATHAK
# This program illustrates an example of Binary Search Tree using Python
class Node(object):
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
def insert(self, data):
''' For inserting the data in the Tree '''
if self.data == data:
return False # As BST cannot contain duplicate data
elif data < self.data:
''' Data less than the root data is placed to the left of the root '''
if self.leftChild:
return self.leftChild.insert(data)
else:
self.leftChild = Node(data)
return True
else:
''' Data greater than the root data is placed to the right of the root '''
if self.rightChild:
return self.rightChild.insert(data)
else:
self.rightChild = Node(data)
return True
def find(self, data):
''' This function checks whether the specified data is in tree or not '''
if(data == self.data):
return True
elif(data < self.data):
if self.leftChild:
return self.leftChild.find(data)
else:
return False
else:
if self.rightChild:
return self.rightChild.find(data)
else:
return False
def preorder(self):
'''For preorder traversal of the BST '''
if self:
print(str(self.data), end = ' ')
if self.leftChild:
self.leftChild.preorder()
if self.rightChild:
self.rightChild.preorder()
def inorder(self):
''' For Inorder traversal of the BST '''
if self:
if self.leftChild:
self.leftChild.inorder()
print(str(self.data), end = ' ')
if self.rightChild:
self.rightChild.inorder()
def postorder(self):
''' For postorder traversal of the BST '''
if self:
if self.leftChild:
self.leftChild.postorder()
if self.rightChild:
self.rightChild.postorder()
print(str(self.data), end = ' ')
class Tree(object):
def __init__(self, initial_data = []):
self.root = None
# If provided, add initial data
for data in initial_data:
self.insert(data)
def insert(self, data):
if self.root:
return self.root.insert(data)
else:
self.root = Node(data)
return True
def find(self, data):
if self.root:
return self.root.find(data)
else:
return False
def preorder(self):
if self.root is not None:
print()
print('Preorder: ')
self.root.preorder()
def inorder(self):
print()
if self.root is not None:
print('Inorder: ')
self.root.inorder()
def postorder(self):
print()
if self.root is not None:
print('Postorder: ')
self.root.postorder()
def pprint(self, head_node=0, _pre="", _last=True, term=False):
head_node = self.root if head_node == 0 else head_node
data = "*" if head_node is None else head_node.data
print(_pre, "`- " if _last else "|- ", data, sep="")
_pre += " " if _last else "| "
if term: return
for i, child in enumerate([head_node.leftChild, head_node.rightChild]):
self.pprint(child, _pre, bool(i) ,term=not(bool(child)))
if __name__ == '__main__':
tree = Tree()
tree.insert(10)
tree.insert(12)
tree.insert(5)
tree.insert(4)
tree.insert(20)
tree.insert(8)
tree.insert(7)
tree.insert(15)
tree.insert(13)
tree.pprint()
print(tree.find(1))
print(tree.find(12))
tree.preorder()
tree.inorder()
tree.postorder()