-
Notifications
You must be signed in to change notification settings - Fork 0
/
app.py
153 lines (125 loc) · 4.37 KB
/
app.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
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
146
147
148
149
150
151
152
153
'''
Binary Tree: In computer science, a binary tree is a tree data structure in which each
node has at most two children, which are referred to as the left child
and the right child.
Binary Search Tree: In computer science, a binary search tree, also called an ordered or sorted
binary tree, is a rooted binary tree whose internal nodes each store a key
greater than all the keys in the node's left subtree and less than those in
its right subtree.
Following are the basic operations of a tree,
- Search: Searches an element in a tree.
- Insert: Inserts an element in a tree.
- Pre-order Traversal: Traverses a tree in a pre-order manner.
- In-order Traversal: Traverses a tree in an in-order manner.
- Post-order Traversal: Traverses a tree in a post-order manner.
'''
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def __str__(self):
return f'Node { self.value }'
def get(self):
return self.value
def set(self, value):
self.value = value
def get_children(self):
children = []
if self.left:
children.append(self.left)
if self.right:
children.append(self.right)
return children
class BinaryTree:
def __init__(self):
self.root = None
def __str__(self):
in_order = ', '.join([f'{ i }' for i in self.in_order(self.root)])
pre_order = ', '.join([f'{ i }' for i in self.pre_order(self.root)])
post_order = ', '.join([f'{ i }' for i in self.post_order(self.root)])
return (
f'Root: { self.root.get() }\n'
f'In-order: { in_order }\n'
f'Pre-order: { pre_order }\n'
f'Post-order: { post_order }\n'
)
def insert(self, value):
if self.root is None:
self.root = Node(value)
else:
self.insert_node(self.root, value)
def insert_node(self, node, value):
if value < node.get():
if node.left:
self.insert_node(node.left, value)
else:
node.left = Node(value)
elif value > node.get():
if node.right:
self.insert_node(node.right, value)
else:
node.right = Node(value)
elif value == node.get():
raise Exception('Unable to add nodes with duplicate values')
else:
raise Exception(f'Unable to determine where to insert { value } beneath node { node.get() }')
def search(self, value):
return self.search_node(self.root, value)
def search_node(self, root, value):
if root:
# print(root.get())
if value == root.get():
return root
if value < root.get():
return self.search_node(root.left, value)
if value > root.get():
return self.search_node(root.right, value)
raise Exception(f'Unable to find node with value { value }')
def search_parent(self, value):
return self.search_parent_node(self.root, value)
def search_parent_node(self, root, value, parent=None):
if root:
# print(root.get())
if value == root.get():
return parent
if value < root.get():
return self.search_parent_node(root.left, value, root)
if value > root.get():
return self.search_parent_node(root.right, value, root)
raise Exception(f'Unable to find node with value { value }')
def pre_order(self, root):
res = []
if root:
res = [root.value]
res += self.pre_order(root.left)
res += self.pre_order(root.right)
return res
def in_order(self, root):
res = []
if root:
res = self.in_order(root.left)
res.append(root.value)
res += self.in_order(root.right)
return res
def post_order(self, root):
res = []
if root:
res = self.post_order(root.left)
res += self.post_order(root.right)
res.append(root.value)
return res
tree = BinaryTree()
tree.insert(7)
tree.insert(2)
tree.insert(3)
tree.insert(5)
tree.insert(13)
tree.insert(523)
tree.insert(6)
tree.insert(31)
tree.insert(52)
tree.insert(17)
print(tree)
print(tree.search(3))
print(tree.search_parent(3))