Welcome, guest | Sign In | My Account | Store | Cart
def printBfsLevels(graph,start):
  queue=[start]
  path=[]
  currLevel=1
  levelMembers=1
  height=[(0,start)]
  childCount=0
  print queue
  while queue:
    visNode=queue.pop(0)
    if visNode not in path:
      if  levelMembers==0:
        levelMembers=childCount
        childCount=0
        currLevel=currLevel+1
      queue=queue+graph.get(visNode,[])
      if levelMembers > 0:
        levelMembers=levelMembers-1
        for node in graph.get(visNode,[]):
          childCount=childCount+1
          height.append((currLevel,node))
      path=path+[visNode]

  prevLevel=None
  
  for v,k in sorted(height):
        if prevLevel!=v:
          if prevLevel!=None:
            print "\n"
        prevLevel=v
        print k,
  return height

g={1: [2, 3,6], 2: [4, 5], 3: [6, 7],4:[8,9,13]}
printBfsLevels(g,1)


>>> 
[1]
1 

2 3 6 

4 5 6 7 

8 9 13
>>> 

# Another version based on Recursion, Which is specific to Binary tree


class BinTree:
  "Node in a binary tree"
  def __init__(self,val,leftChild=None,rightChild=None,root=None):
    self.val=val
    self.leftChild=leftChild
    self.rightChild=rightChild
    self.root=root
    if not leftChild and not rightChild:
      self.isExternal=True

  def getChildren(self,node):
    children=[]
    if node.isExternal:
      return []
    if node.leftChild:
      children.append(node.leftChild)
    if node.rightChild:
      children.append(node.rightChild)
    return children

  @staticmethod
  def createTree(tupleList):
    "Creates a Binary tree Object from a given Tuple List"
    Nodes={}
    root=None
    for item in treeRep:
      if not root:
        root=BinTree(item[0])
        root.isExternal=False
        Nodes[item[0]]=root
        root.root=root
        root.leftChild=BinTree(item[1],root=root)
        Nodes[item[1]]=root.leftChild
        root.rightChild=BinTree(item[2],root=root)
        Nodes[item[2]]=root.rightChild
      else:
        CurrentParent=Nodes[item[0]]
        CurrentParent.isExternal=False
        CurrentParent.leftChild=BinTree(item[1],root=root)
        Nodes[item[1]]=CurrentParent.leftChild
        CurrentParent.rightChild=BinTree(item[2],root=root)
        Nodes[item[2]]=CurrentParent.rightChild
    root.nodeDict=Nodes
    return root

  def printBfsLevels(self,levels=None):
    if levels==None:
      levels=[self]
    nextLevel=[]
    for node in levels:
      print node.val,
    for node in levels:
      nextLevel.extend(node.getChildren(node))
    print '\n'
    if nextLevel:
      node.printBfsLevels(nextLevel)  
     

##       1
##     2     3
##   4   5  6  7
##  8

treeRep = [(1,2,3),(2,4,5),(3,6,7),(4,8,None)]
tree= BinTree.createTree(treeRep)
tree.printBfsLevels()

>>> 
1 

2 3 

4 5 6 7 

8 None 

Diff to Previous Revision

--- revision 3 2011-09-22 13:48:54
+++ revision 4 2011-09-28 12:06:25
@@ -45,3 +45,82 @@
 
 8 9 13
 >>> 
+
+# Another version based on Recursion, Which is specific to Binary tree
+
+
+class BinTree:
+  "Node in a binary tree"
+  def __init__(self,val,leftChild=None,rightChild=None,root=None):
+    self.val=val
+    self.leftChild=leftChild
+    self.rightChild=rightChild
+    self.root=root
+    if not leftChild and not rightChild:
+      self.isExternal=True
+
+  def getChildren(self,node):
+    children=[]
+    if node.isExternal:
+      return []
+    if node.leftChild:
+      children.append(node.leftChild)
+    if node.rightChild:
+      children.append(node.rightChild)
+    return children
+
+  @staticmethod
+  def createTree(tupleList):
+    "Creates a Binary tree Object from a given Tuple List"
+    Nodes={}
+    root=None
+    for item in treeRep:
+      if not root:
+        root=BinTree(item[0])
+        root.isExternal=False
+        Nodes[item[0]]=root
+        root.root=root
+        root.leftChild=BinTree(item[1],root=root)
+        Nodes[item[1]]=root.leftChild
+        root.rightChild=BinTree(item[2],root=root)
+        Nodes[item[2]]=root.rightChild
+      else:
+        CurrentParent=Nodes[item[0]]
+        CurrentParent.isExternal=False
+        CurrentParent.leftChild=BinTree(item[1],root=root)
+        Nodes[item[1]]=CurrentParent.leftChild
+        CurrentParent.rightChild=BinTree(item[2],root=root)
+        Nodes[item[2]]=CurrentParent.rightChild
+    root.nodeDict=Nodes
+    return root
+
+  def printBfsLevels(self,levels=None):
+    if levels==None:
+      levels=[self]
+    nextLevel=[]
+    for node in levels:
+      print node.val,
+    for node in levels:
+      nextLevel.extend(node.getChildren(node))
+    print '\n'
+    if nextLevel:
+      node.printBfsLevels(nextLevel)  
+     
+
+##       1
+##     2     3
+##   4   5  6  7
+##  8
+
+treeRep = [(1,2,3),(2,4,5),(3,6,7),(4,8,None)]
+tree= BinTree.createTree(treeRep)
+tree.printBfsLevels()
+
+>>> 
+1 
+
+2 3 
+
+4 5 6 7 
+
+8 None 

History