In [1]:
class TreeNode(object):
"""
"""
def __init__(self,x,left=None,right=None):
self.val = x
self.left = left
self.right = right
def __str__(self):
return "%d" % self.val
def insert(root, data):
if not root:
root = TreeNode(data)
else:
if data < root.val:
if root.left is None:
root.left = TreeNode(data)
else:
insert(root.left,data)
else:
if root.right is None:
root.right = TreeNode(data)
else:
insert(root.right,data)
In [42]:
head = TreeNode(8)
insert(head, 3)
insert(head, 10)
insert(head, 1)
insert(head, 6)
insert(head, 4)
insert(head, 7)
insert(head, 14)
insert(head, 13)
In [57]:
print " BFS: \t",
BFS(head)
print "\n\n recursivePreorder: \t",
recursivePreorder(head)
print "\n recursiveInorder: \t",
recursiveInorder(head)
print "\n recursivePostorder: \t",
recursivePostorder(head)
print "\n\n iterativePreorder: \t",
iterativePreorder(head)
print "\n iterativeInorder: \t",
iterativeInorder(head)
print "\n iterativePostorder: \t",
iterativePostorder3(head)
In [52]:
def BFS(root):
queue = [root]
while queue:
node = queue.pop()
if node.left is not None:
queue.insert(0,node.left)
if node.right is not None:
queue.insert(0,node.right)
print node.val,
def recursivePreorder(root):
if root is None:
return
print root.val,
recursivePreorder(root.left)
recursivePreorder(root.right)
def recursiveInorder(root):
if root is None:
return
recursiveInorder(root.left)
print root.val,
recursiveInorder(root.right)
def recursivePostorder(root):
if root is None:
return
recursivePostorder(root.left)
recursivePostorder(root.right)
print root.val,
def iterativePreorder(root):
if root is None:
return
stack = [root]
current = root
while stack:
# Pop the top item from stack and print it
node = stack.pop()
print node.val,
# Note that right child is pushed first so that left
# is processed first
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
def iterativeInorder(root):
current = root
s = []
done = 0
while(len(s) >0 or current is not None):
# Reach the left most Node of the current Node
if current is not None:
s.append(current)
current = current.left
# BackTrack from the empty subtree and visit the Node
# at the top of the stack; however, if the stack is
# empty you are done
else:
current = s.pop()
print current.val,
# We have visited the node and its left
# subtree. Now, it's right subtree's turn
current = current.right
def iterativePostorder(root):
if root is None:
return
stack = [root]
while stack:
temp = stack[-1]
if(temp.left is None and temp.right is None):
pop = stack.pop()
print pop.val,
else:
if(temp.right is not None):
stack.append(temp.right)
temp.right = None
if(temp.left is not None):
stack.append(temp.left)
temp.left = None
def peek(stack):
if len(stack) > 0:
return stack[-1]
#http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/
def iterativePostorder2(root):
# Check for empty tree
if root is None:
return
stack = []
while(True):
while (root):
# Push root's right child and then root to stack
if root.right is not None:
stack.append(root.right)
stack.append(root)
# Set root as root's left child
root = root.left
# Pop an item from stack and set it as root
root = stack.pop()
# If the popped item has a right child and the
# right child is not processed yet, then make sure
# right child is processed before root
if (root.right is not None and
peek(stack) == root.right):
stack.pop() # Remove right child from stack
stack.append(root) # Push root back to stack
root = root.right # change root so that the
# righ childis processed next
# Else print root's data and set root as None
else:
print root.val,
root = None
if (len(stack) <= 0):
break
#http://www.geeksforgeeks.org/iterative-postorder-traversal/
def iterativePostorder3(root):
if root is None:
return
# Create two stacks
s1 = []
s2 = []
# Push root to first stack
s1.append(root)
# Run while first stack is not empty
while (len(s1) >0):
# Pop an item from s1 and append it to s2
node = s1.pop()
s2.append(node)
# Push left and right children of removed item to s1
if node.left is not None:
s1.append(node.left)
if node.right is not None :
s1.append(node.right)
# Print all eleements of second stack
while(len(s2) > 0):
node = s2.pop()
print node.val,
In [15]:
graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C','F'],
'E': ['F'],
'F': ['C']}
print "One path: \t", find_path(graph,'A', 'D')
print "Shortest path: \t", find_min_path(graph,'A', 'D')
print "All paths: \t", find_all_paths(graph,'A', 'D')
In [3]:
def find_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath: return newpath
return None
def find_all_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not graph.has_key(start):
return []
all_paths = []
for node in graph[start]:
if node not in path:
newpaths = find_all_paths(graph, node, end, path)
for newpath in newpaths:
all_paths.append(newpath)
return all_paths
def find_min_path(graph, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not graph.has_key(start):
return None
optimal_path = None
for node in graph[start]:
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath:
if not optimal_path or len(newpath)<len(optimal_path):
optimal_path = newpath
return optimal_path