class BinaryTree:
def __init__(self, root):
self.root = root
self.leftChild = None
self.rightChild = None
def setRoot(self, root):
self.root = root
def getRoot(self):
return self.root
def getLeftChild(self):
return self.leftChild
def getRightChild(self):
return self.rightChild
def insertLeftChild(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRightChild(self, newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
def getNumberOfLeavesIterative(tree):
queue = []
leafCount = 0
queue.append(tree)
if tree == None:
return 0
while (queue != []):
temp = queue.pop(0)
if temp.getLeftChild() == None and temp.getRightChild() == None:
leafCount += 1
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())
return leafCount
def getNumberOfNonLeafNodesIterative(tree):
queue = []
nonleafCount = 0
queue.append(tree)
if tree == None:
return 0
while (queue != []):
temp = queue.pop(0)
if temp.getLeftChild() != None and temp.getRightChild() != None:
nonleafCount += 1
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())
return nonleafCount
def getNumberOfNodesHavingOneChild(tree):
queue = []
oneChildCount = 0
queue.append(tree)
if tree == None:
return 0
while (queue != []):
temp = queue.pop(0)
if (temp.getLeftChild() == None and temp.getRightChild() != None) or(temp.getLeftChild() != None and temp.getRightChild() == None) :
oneChildCount += 1
if temp.getLeftChild():
queue.append(temp.getLeftChild())
if temp.getRightChild():
queue.append(temp.getRightChild())
return oneChildCount
if __name__ == "__main__":
r = BinaryTree(5)
r.insertLeftChild(6)
r.insertRightChild(7)
r.leftChild.insertLeftChild(12)
r.leftChild.insertRightChild(54)
r.rightChild.insertRightChild(63)
print "The number of leaf nodes of the binary tree are:",getNumberOfNonLeafNodesIterative(r)
print "\n\n"
print "The number of non-leaf nodes of the binary tree are:", getNumberOfNonLeafNodesIterative(r)
print "\n\n"
print "The number of nodes having just one child are:", getNumberOfNodesHavingOneChild(r)
print "\n\n"
Like this:
Like Loading...
Related
Pingback: Tree Walks and Traversals | codeatsociallywired