Due Monday Apr 24 at 9pm. Upload to Desire 2 Learn dropbox for homework 10.
This homework exercise will allow you to explore adding an iterator to a class to print a binary tree in breadth first order. See the following to get started.
Start here: hw_11_starter.py
Implement bforder() as a generator that yields each element in the tree in breadth first order.
Implement build_tree so it loads the data in list into the tree. See code for more info.
Rename the source code file containing your version of the program according to syllabus.
"""
A BinaryTree class implemented with node/reference technique
solution.py hw11
"""
from collections import deque
class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
def insertLeft(self,newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRight(self,newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
def setRootVal(self,obj):
self.key = obj
def getRootVal(self):
return self.key
def preorder(self):
print self.key,
if self.leftChild:
self.leftChild.preorder()
if self.rightChild:
self.rightChild.preorder()
def inorder(self):
if self.leftChild:
self.leftChild.inorder()
print(self.key),
if self.rightChild:
self.rightChild.inorder()
def postorder(self):
if self.leftChild:
self.leftChild.postorder()
if self.rightChild:
self.rightChild.postorder()
print(self.key),
def bforder(self):
q = deque([self])
while q:
p = q.popleft()
yield p.getRootVal()
children = p.getLeftChild(), p.getRightChild()
for i in children:
if i: q.append(i)
def build_tree(self, tree, pos, data):
if 2*pos > len(data)-1:
return
tree.insertLeft(data[2*pos])
self.build_tree(tree.getLeftChild(), 2*pos, data)
tree.insertRight(data[2*pos+1])
self.build_tree(tree.getRightChild(), 2*pos+1, data)
if __name__ == '__main__':
data = [0]
data.extend('guoidpy') # --> [0, 'g', 'u', 'o', 'i', 'd', 'p', 'y']
print '\nInput Data ==>\t', data
root = BinaryTree(data[1])
root.build_tree(root, 1, data)
print '\nBuilding the tree with root =', root.getRootVal()
###### tree structure: ######
# #
# g #
# ____|____ #
# u o #
# __|__ __|__ #
# i d p y #
# #
#############################
print '\n Pre Order ==>\t', # --> g u i d o p y
root.preorder()
print '\n In Order ==>\t', # --> i u d g p o y
root.inorder()
print '\nPost Order ==>\t', # --> i d u p y o g
root.postorder()
print '\n BF Order ==>\t', # --> g u o i d p y
for i in root.bforder(): print i,