document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. class BinTree:
  2.   "Node in a binary tree"
  3.   def __init__(self,val,leftChild=None,rightChild=None,root=None):
  4.     self.val=val
  5.     self.leftChild=leftChild
  6.     self.rightChild=rightChild
  7.     self.root=root
  8.     if not leftChild and not rightChild:
  9.       self.isExternal=True
  10.  
  11.   def getChildren(self,node):
  12.     children=[]
  13.     if node.isExternal:
  14.       return []
  15.     if node.leftChild:
  16.       children.append(node.leftChild)
  17.     if node.rightChild:
  18.       children.append(node.rightChild)
  19.     return children
  20.  
  21.   @staticmethod
  22.   def createTree(tupleList):
  23.     "Creates a Binary tree Object from a given Tuple List"
  24.     Nodes={}
  25.     root=None
  26.     for item in treeRep:
  27.       if not root:
  28.         root=BinTree(item[0])
  29.         root.isExternal=False
  30.         Nodes[item[0]]=root
  31.         root.root=root
  32.         root.leftChild=BinTree(item[1],root=root)
  33.         Nodes[item[1]]=root.leftChild
  34.         root.rightChild=BinTree(item[2],root=root)
  35.         Nodes[item[2]]=root.rightChild
  36.       else:
  37.         CurrentParent=Nodes[item[0]]
  38.         CurrentParent.isExternal=False
  39.         CurrentParent.leftChild=BinTree(item[1],root=root)
  40.         Nodes[item[1]]=CurrentParent.leftChild
  41.         CurrentParent.rightChild=BinTree(item[2],root=root)
  42.         Nodes[item[2]]=CurrentParent.rightChild
  43.     root.nodeDict=Nodes
  44.     return root
  45.  
  46.   def printBfsLevels(self,levels=None):
  47.     if levels==None:
  48.       levels=[self]
  49.     nextLevel=[]
  50.     for node in levels:
  51.       print node.val,
  52.     for node in levels:
  53.       nextLevel.extend(node.getChildren(node))
  54.     print \'\\n\'
  55.     if nextLevel:
  56.       node.printBfsLevels(nextLevel)  
  57.      
  58.  
  59. ##       1
  60. ##     2     3
  61. ##   4   5  6  7
  62. ##  8
  63.  
  64. treeRep = [(1,2,3),(2,4,5),(3,6,7),(4,8,None)]
  65. tree= BinTree.createTree(treeRep)
  66. tree.printBfsLevels()
  67.  
  68. >>>
  69. 1
  70.  
  71. 2 3
  72.  
  73. 4 5 6 7
  74.  
  75. 8 None
  76.  
  77.  
');