-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_tree.py
119 lines (105 loc) · 3.75 KB
/
binary_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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
# Binary Tree
class Node:
# Initializing the binary tree to create nodes. Left and right children are none by default
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Function to insert a node
def insert(self, value):
# self.key is nothing but the root.
if self.key is None:
# by default the first value to be inserted will be the root node unless it's modified in the program
self.key = value
return
# To ignore duplicates
if self.key == value:
pass
elif value < self.key: # Check the rules of binary tree
if self.left: # Evaluated to either true (present) or false (not present)
self.left.insert(value)
else: # Otherwise a left child node will be created for the original root node
self.left = Node(value)
else:
if self.right:
self.right.insert(value)
else:
self.right = Node(value)
# Function to search in the tree
def search(self, value):
if value == self.key:
print("Node found")
return
if value < self.key:
if self.left:
# This will be the parameter to be passed to the function and then compared with the value
self.left.search(value)
else:
print("Node is not present in the tree")
else:
if self.right:
self.right.search(value)
else:
print("Node is not present in the tree")
# Traversals:
# r = root
def inorder(r):
# Left -> Root -> Right
if r:
inorder(r.left)
print(r.key)
inorder(r.right)
def preorder(r):
# Root -> Left -> Right
if r:
print(r.key)
preorder(r.left)
preorder(r.right)
def postorder(r):
# Left -> Right -> Root
if r:
postorder(r.left)
postorder(r.right)
print(r.key)
root = Node(10) # we can also set the root node manually
data = [6, 3, 1, 6, 98, 3, 7]
for nodes in data:
root.insert(nodes) # accessing the function insert() from class/TYPE Node
#--------------------------------------------------------------------------#
# The representation of the nodes in data will be as follows:::: #
# #
# 10 #
# / \ #
# 6 98 #
# / \ #
# 3 7 #
# / #
# 1 #
#--------------------------------------------------------------------------#
# Below code is just an illustration for the code runner to see how the function works.
while True:
try:
opt = int(input("""
Choose an option:
1. Search for a node
2. Display nodes
3. exit
> """))
if opt == 1:
node = int(input("Enter the node you are looking for: "))
root.search(node)
elif opt == 2:
t = int(input("1. Inorder, 2. Pre-order, 3. Post-order: "))
print("")
if t == 1:
inorder(root)
elif t == 2:
preorder(root)
elif t == 3:
postorder(root)
elif opt == 3:
exit()
# else:
# pass
except Exception as e:
print(e)