About
hello world
from collections import OrderedDict
class BinHeap(): def __init__(self): self.heapList = [0] self.currentSize = 0
""" This method defines the upheap function when inserting an element
"""
def upHeapp(self, i):
while i // 2 > 0:
if self.heapList[i] < self.heapList[i // 2]:
self.heapList[i], self.heapList[i // 2] = self.heapList[i // 2], self.heapList[i]
i = i // 2
def insert(self, k):
self.heapList.append(k)
self.currentSize += 1
self.upHeapp(self.currentSize)
def size(self):
return self.currentSize
""" This method defines the downheap function when removing min
"""
def downHeap(self, i):
while (i * 2) <= self.currentSize:
min = self.minChild(i)
if self.heapList[i] > self.heapList[min]:
self.heapList[i], self.heapList[min] = self.heapList[min], self.heapList[i]
i = min
def minChild(self, i):
if (i * 2) + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i * 2] < self.heapList[(i * 2) + 1]:
return i * 2
else:
return (i * 2) + 1
def delMin(self):
if len(self.heapList) == 1:
return 'Empty heap'
root = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.heapList.pop(self.currentSize)
self.currentSize -= 1
self.downHeap(1)
# self.printHeap()
return root
# create a method to print the contents of the heap in level order
def printHeap(self):
print(self.heapList)
'''
Graph ADT starts from here
'''class Vertex: def _init_(self, key): self.id = key self.connectedTo = {}
def addNeighbor(self, nbr, weight=0):
self.connectedTo[nbr] = weight
def _str_(self):
return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self, nbr):
return self.connectedTo[nbr]class Graph: def _init_(self): self.vertList = {} self.numVertices = 0 self.front = [] self.back = [] self.depfs = []
def addVertex(self, key):
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertList[key] = newVertex
self.vertList = OrderedDict(sorted(self.vertList.items()))
return newVertex
def getVertex(self, n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def _contains_(self, n):
return n in self.vertList
def addEdge(self, f, t, cost=0): # f is from node, t is to node
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost)
def getVertices(self):
return self.vertList.keys()
def _iter_(self):
return iter(self.vertList.values())
"""
Write a method to generate an adjacency matrix representation of the graph
"""
def createAdjMatrix(self):
adjmat = list()
# @start-editable@
for i in self.vertList:
tmp = [0] * self.numVertices
for j in self.vertList[i].connectedTo:
tmp[j.id] = self.vertList[i].connectedTo[j]
adjmat.append(tmp)
# @end-editable@
print("Adjacency matrix")
for i in range(self.numVertices):
for j in range(self.numVertices):
print(adjmat[i][j], end=" ")
print("")
return
def printdfs(self):
print("Front edges:", self.front)
print("Back edges:", self.back)
print("dfs:", self.depfs)
"""
Write a method to traverse the graph using dfs from start node.
The function must print the nodes and edges in the order in which
they are visited, and mention if it is a forward or backward edge.
"""
def dfs(self, stnode):
self.depfs.append(stnode.getId())
neighbours = list(stnode.getConnections())
# @start-editable@
for i in neighbours:
if i.getId() not in self.depfs:
self.front.append([stnode.getId(), i.getId()])
self.dfs(i)
else:
self.back.append([stnode.getId(), i.getId()])
# @end-editable@
return
"""
Write a method to traverse the graph using bfs from start node. The function must print the nodes and edges in the order in which
they are visited, and mention if it is a forward or cross edge.
"""
def bfs(self, stnode):
queue = []
breadth = []
cross = []
breadth.append(stnode.getId())
queue.append(stnode.getId())
# @start-editable@
while queue:
tmp = queue.pop(0)
for i in list(self.vertList[tmp].getConnections()):
if i.getId() not in breadth:
breadth.append(i.getId())
queue.append(i.getId())
else:
cross.append([self.vertList[tmp].getId(), i.getId()])
# @end-editable@
print("Bfs:", breadth)
print("Cross edge:", cross)
return
"""
Write a method to generate the minimum spanning tree of the graph using Kruskal algorithm
"""
def mstKruskal(self):
wt = BinHeap()
edge = {}
tree = []
re = []
# @start-editable@
for i in self.vertList:
tree.append({i})
for j in self.vertList[i].getConnections():
wt.insert([self.vertList[i].connectedTo[j], i, j.getId()])
while wt.currentSize:
tmp = wt.delMin()
for i in tree:
if tmp[1] in i:
c_u = i
if tmp[2] in i:
c_v = i
if c_u != c_v:
re.append([tmp[1], tmp[2]])
tmp = c_u.union(c_v)
tree.remove(c_u)
tree.remove(c_v)
tree.append(tmp)
# @end-editable@
print("Minimum spanning tree:", sorted(re))
returndef testGraph(): g = Graph() for i in range(6): g.addVertex(i) g.vertList g.addEdge(5, 1, 8) g.addEdge(1, 2, 19) g.addEdge(5, 0, 10) g.addEdge(4, 6, 11) g.addEdge(6, 10, 23) g.addEdge(10, 9, 33) g.addEdge(9, 8, 7) g.addEdge(6, 7, 6) g.addEdge(8, 7, 1) g.addEdge(9, 6, 9) g.addEdge(7, 10, 14) g.addEdge(0, 4, 15) g.addEdge(0, 3, 16) g.addEdge(0, 2, 5) g.addEdge(0, 1, 2) g.addEdge(2, 3, 4) g.addEdge(3, 4, 30) g.addEdge(4, 5, 18) g.addEdge(5, 2, 22) g.addEdge(3, 1, 17)
for v in g:
for w in v.getConnections():
print("( %s , %s )" % (v.getId(), w.getId()))
inputs = int(input())
while inputs > 0:
command = input()
operation = command.split()
if (operation[0] == "A"):
AdjMat = g.createAdjMatrix()
elif (operation[0] == "B"):
start = g.getVertex(int(operation[1]))
g.bfs(start)
elif (operation[0] == "D"):
start = g.getVertex(int(operation[1]))
g.dfs(start)
g.printdfs()
elif (operation[0] == "M"):
g.mstKruskal()
inputs -= 1def main(): testGraph()
if __name__ == '__main__': main()
binary treefrom re import S
class BinaryTree: class node: def __init__(self): self.element = 0 self.parent = None self.leftchild = None self.rightchild = None
def __init__(self):
self.sz = 0
self.root = self.node()
self.ht = 0
def getChildren(self, curnode):
children = []
if curnode.leftchild != None:
children.append(curnode.leftchild)
if curnode.rightchild != None:
children.append(curnode.rightchild)
return children
def isExternal(self, curnode):
if (curnode.leftchild==None and curnode.rightchild==None):
return (True)
else:
return (False)
def isRoot(self,curnode):
if (curnode.parent==None):
return True
else:
return False
def inorderTraverse(self, v):
#@start-editable@
if v:
self.inorderTraverse(v.leftchild)
print(v.element, end=",")
self.inorderTraverse(v.rightchild)
#@end-editable@
def preorderTraverse(self, v):
#@start-editable@
if v:
print(v.element, end=",")
self.preorderTraverse(v.leftchild)
self.preorderTraverse(v.rightchild)
#@end-editable@
def postorderTraverse(self, v):
#@start-editable@
if v:
self.postorderTraverse(v.leftchild)
self.postorderTraverse(v.rightchild)
print(v.element, end=",")
#@end-editable@
def levelorderTraverse(self, v):
#@start-editable@
h = self.findHeight(v)
def printLevel(v, level):
if v is None:
return
if level == 1:
print(v.element, end=",")
else:
printLevel(v.leftchild, level-1)
printLevel(v.rightchild, level-1)
for i in range(h+2):
printLevel(v, i)
#@end-editable@
def findDepth(self, v):
#@start-editable@
temp = v.parent
ans = 0
while temp is not None:
ans += 1
temp = temp.parent
return ans
#@end-editable@
def findHeight(self, v):
#@start-editable@
if v is None:
return -1
left = self.findHeight(v.leftchild)
right = self.findHeight(v.rightchild)
return max(left, right) + 1
#@end-editable@
# delete leaves in the tree
def delLeaves(self, v):
#@start-editable@
if self.isExternal(v):
return None
if v is None:
return None
v.leftchild = self.delLeaves(v.leftchild)
v.rightchild = self.delLeaves(v.rightchild)
# return v
#@end-editable@
# returns true if tree is proper
def isProper(self, v):
#@start-editable@
def rec(root):
if root is None:
return True
if self.isExternal(root):
return True
# If both left and right subtress are not None and
if root.leftchild is not None and root.rightchild is not None:
return (rec(root.leftchild) and rec(root.rightchild))
# We reach here when none of the above if conditions work
return False
return rec(self.root)
#@end-editable@
# create a tree that is a mirror image of the original tree and print its levelorder
def mirror(self, v):
#@start-editable@
# def mir(l, r):
# if l is None and r is None:
# return
# l.element, r.element = r.element, l.element
# mir(l.leftchild, r.rightchild)
# mir(l.rightchild, r.leftchild)
# if v is None:
# return
# mir(v.leftchild, v.rightchild)
queue = []
if v is not None:
queue.append(v)
while queue:
x = queue.pop(0)
temp = x.leftchild
x.leftchild = x.rightchild
x.rightchild = temp
if x.leftchild:
queue.append(x.leftchild)
if x.rightchild:
queue.append(x.rightchild)
#@end-editable@
def buildTree(self, eltlist):
nodelist = []
nodelist.append(None)
for i in range(len(eltlist)):
if (i != 0):
if (eltlist[i] != -1):
tempnode = self.node()
tempnode.element = eltlist[i]
if i != 1:
tempnode.parent = nodelist[i // 2]
if (i % 2 == 0):
nodelist[i // 2].leftchild = tempnode
else:
nodelist[i // 2].rightchild = tempnode
nodelist.append(tempnode)
else:
nodelist.append(None)
self.root = nodelist[1]
self.sz=len(nodelist)
return nodelist
# write a function to visualize the tree
def printTree(self, nlist):
for i in range(len(nlist)):
if (nlist[i] != None):
print(nlist[i].element,end=" ");
else:
print(None)
def isEmpty(self):
return (self.sz == 0)
def size(self):
return self.sz
#determine whether there exists a root-to-leaf path whose nodes sum is equal to a specified integer
def root2leafsum(self, k):
#@start-editable@
def rec(root, n, k):
if root is None:
return 0
sum = n + root.element
if self.isExternal(root) and sum == k:
return 1
return rec(root.leftchild, sum, k) + rec(root.rightchild, sum, k)
print(rec(self.root, 0, k) >= 1)
return
#@end-editable@
#determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.
def leastleaf(self):
#@start-editable@
def rec(root, s, n):
if self.isExternal(root):
return (s + root.element, root.element)
sum = s + root.element
l = rec(root.leftchild, sum, 0) if root.leftchild is not None else (sum, -1)
r = rec(root.rightchild, sum, 0) if root.rightchild is not None else (sum, -1)
print(l, r)
if l[1] == -1:
return r
elif r[1] == -1:
return l
else:
return (l if l[0] < r[0] else r)
print(rec(self.root, 0, 0)[1])
#@end-editable@tree = BinaryTree() arraySize = int(input()) arr = list(map(int, input().split())) nlist = tree.buildTree(arr) inputs = int(input()) while inputs > 0: command = input() operation = command.split() if (operation[0] == "I"): tree.inorderTraverse(tree.root) print() elif (operation[0] == "P"): tree.preorderTraverse(tree.root) print() elif (operation[0] == "Post"): tree.postorderTraverse(tree.root) print() elif (operation[0] == "L"): tree.levelorderTraverse(tree.root) print() elif (operation[0] == "D"): pos = int(operation[1]) print(tree.findDepth(nlist[pos])) elif (operation[0] == "H"): pos = int(operation[1]) print(tree.findHeight(nlist[pos])) elif (operation[0] == "IP"): print(tree.isProper(tree.root)) elif (operation[0] == 'M'): tree.mirror(tree.root) tree.levelorderTraverse(tree.root) print() elif (operation[0] == 'DL'): tree.delLeaves(tree.root) tree.levelorderTraverse(tree.root) print() elif (operation[0] == 'RL'): tree.root2leafsum(int(operation[1])) print() elif (operation[0] == 'ML'): tree.leastleaf() print() inputs -= 1
bstfrom queue import Queue
class node: def __init__(self, val): self.left = None self.right = None self.data = val
def insert(self, val):
if self.data:
if val < self.data:
if self.left is None:
self.left = node(val)
else:
self.left.insert(val)
elif self.data < val:
if self.right is None:
self.right = node(val)
else:
self.right.insert(val)
else:
self.data = val
def inorder(self, root):
if root:
self.inorder(root.left)
print(root.data)
self.inorder(root.right)
def preorder(self, root):
if root:
print(root.data)
self.inorder(root.left)
self.inorder(root.right)
def postorder(self, root):
if root:
self.inorder(root.left)
self.inorder(root.right)
print(root.data)
def levelorder(self, root):
q = Queue()
q.put(root)
while not q.empty():
x = q.get()
if x is None:
continue
print(x.data)
q.put(x.left)
q.put(x.right)root = node(97) root.insert(98) root.insert(99) root.insert(101) root.insert(102) root.insert(103) root.insert(104) root.insert(105) root.insert(106) root.insert(107) root.insert(108) root.insert(109) root.insert(110) root.insert(111) root.insert(112) root.insert(113) root.insert(114) root.insert(115) root.insert(116) root.insert(117) root.insert(118) root.insert(119) root.insert(120) root.insert(121) root.insert(122)
root.inorder(root) print(" ")