Repository navigation
Expand file tree
/
Copy pathP43_BinarySearchTree.py
More file actions
124 lines (108 loc) · 3.34 KB
/
Copy pathP43_BinarySearchTree.py
File metadata and controls
124 lines (108 loc) · 3.34 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
# 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):
self.root = None
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()
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)
print(tree.find(1))
print(tree.find(12))
tree.preorder()
tree.inorder()
tree.postorder()