-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path4.08.py
More file actions
200 lines (176 loc) · 8.02 KB
/
4.08.py
File metadata and controls
200 lines (176 loc) · 8.02 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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
'''
Author: McSteve Ezikeoha
Title: Binary Search Trees
Date: May 6, 2018
'''
# Problem 4.8: find_anywhere(some_node, value)
# even if the tree is not a BST, find the node whose value is given and return
# the pointer to that node. Use the preorder traversal algorithm to search.
# (recursive, stop when found)
class BST:
class Node:
def __init__(self, payload):
self.payload = payload
self.left = None
self.right = None
def __init__(self):
self.root = None
def prettyprint(self):
BST.prettyprint_aux(self.root, 0)
def prettyprint_aux(somenode, indentLevel):
if somenode.right != None:
BST.prettyprint_aux(somenode.right, indentLevel+1)
for k in range(indentLevel):
print(" ", end="")
print(somenode.payload)
print()
if somenode.left != None:
BST.prettyprint_aux(somenode.left, indentLevel+1)
def find(self, target):
return BST.find_aux(self.root, target)
def find_aux(treeptr, target):
if treeptr == None:
return None
if treeptr.payload == target:
return treeptr
elif target < treeptr.payload:
return BST.find_aux(treeptr.left, target)
else: # look in right subtree
return BST.find_aux(treeptr.right, target)
def attach_in_order(self, new_value):
if self.root == None:
self.root = BST.Node(new_value)
else:
BST.attach_in_order_aux(self.root, new_value)
def attach_in_order_aux(treeptr, new_value):
if new_value < treeptr.payload:
if treeptr.left == None:
treeptr.left = BST.Node(new_value)
else:
BST.attach_in_order_aux(treeptr.left, new_value)
elif new_value > treeptr.payload:
if treeptr.right == None:
treeptr.right = BST.Node(new_value)
else:
BST.attach_in_order_aux(treeptr.right, new_value)
def isLeaf(some_node):
if some_node.left == None and some_node.right == None:
return False
else:
return True
def getPath(self, some_node):
pathList = []
runner = self.root
pathList.append(runner)
while runner != None and runner != some_node:
if runner.payload > some_node.payload:
runner = runner.left
pathList.append(runner)
else:
runner = runner.right
pathList.append(runner)
return pathList
def find_parent(self, some_node):
if self.root == some_node:
return None
runner = self.root
parent = self.root
while runner != None and runner != some_node:
if runner.payload > some_node.payload:
parent = runner
runner = runner.left
else:
parent = runner
runner = runner.right
return parent
def isBST(some_node):
if some_node.left == None and some_node.right == None:
return True
if some_node.left != None:
if some_node.left.payload > some_node.payload:
return False
else:
return BST.isBST(some_node.left)
if some_node.right != None:
if some_node.right.payload < some_node.payload:
return False
else:
return BST.isBST(some_node.right)
else:
return True
def flip(self):
BST.flip_aux(self.root)
def flip_aux(some_node):
runner = some_node
temp = some_node
if runner == None:
return None
if runner.left != None or runner.right != None:
temp = runner.left
runner.left = runner.right
runner.right = temp
return BST.flip_aux(some_node.left), BST.flip_aux(some_node.right)
def traverse(some_node, order):
nodes = []
if order == "preorder":
def _traverse_pre_order_aux(some_node):
if not some_node:
return
nodes.append(some_node)
if some_node.left != None:
_traverse_pre_order_aux(some_node.left)
if some_node.right != None:
_traverse_pre_order_aux(some_node.right)
_traverse_pre_order_aux(some_node)
return nodes
elif order == "inorder":
def _traverse_in_order_aux(some_node):
if not some_node:
return
if some_node.left != None:
_traverse_in_order_aux(some_node.left)
nodes.append(some_node)
if some_node.right != None:
_traverse_in_order_aux(some_node.right)
_traverse_in_order_aux(some_node)
return nodes
elif order == "postorder":
def _traverse_post_order_aux(some_node):
if not some_node:
return
if some_node.left != None:
_traverse_post_order_aux(some_node.left)
if some_node.right != None:
_traverse_post_order_aux(some_node.right)
nodes.append(some_node)
_traverse_post_order_aux(some_node)
return nodes
else:
print("traverse the tree whose root is some_node in 'inorder'",
"'preorder' or 'postorder'")
def find_anywhere(some_node, value):
search = BST.traverse(some_node, "preorder")
for node in search:
if node.payload == value:
return node
if __name__ == "__main__":
tree = BST()
tree.root = BST.Node("man")
tree.attach_in_order("dog")
tree.attach_in_order("zebra")
tree.attach_in_order("ape")
tree.attach_in_order("elephant")
tree.attach_in_order("yak")
tree.attach_in_order("zorse")
tree.attach_in_order("fly")
tree.prettyprint()
node = BST.find_anywhere(tree.root, "yak")
if node is None:
print("yak node not found")
else:
print("yak found at node: ",node.payload)
node = BST.find_anywhere(tree.root, "octopus")
if node is None:
print("octopus node not found")
else:
print("octopus found at node: ",node.payload)