Python Abstract Data Types
An abstract data type (ADT).
Binary Tree
How it works:
the BinaryTree class
Ref: "Problem solving with algorithms and data structures using python", Bradley N. Miller and David L. Ranum (2006)
class BinaryTree:
def __init__(self,rootObj):
self.key = rootObj
self.left = None
self.right = None
def insertLeft(self,newNode):
if self.left == None:
self.left = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.left = self.left
self.left = t
def insertRight(self,newNode):
if self.right == None:
self.right = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.right = self.right
self.right = t
def getRootVal(self,):
return self.key
def setRootVal(self,obj):
self.key = obj
def getLeftChild(self):
return self.left
def getRightChild(self):
return self.right
the main program
#! /usr/bin/env python
# -*- coding: cp1252 -*-
# Binary tree test by Benny Skogberg 3 februari 2009
from BinTre import *
print "=" * 70
print " " * 27, "Binary tree test"
print "=" * 70
a = BinaryTree('a')
a.insertLeft('b')
a.insertRight('c')
print " a = BinaryTree('a') # assign object to (a) with value (a)"
print " a.insertLeft('b') # add left child (b) to (a)"
print " a.insertRight('c') # add right child (c) to (a)"
print
print ' a '
print ' / \ # the Tree as of now'
print ' b c '
print
b = a.getLeftChild()
b.insertLeft('d')
b.insertRight('e')
print " b = a.getLeftChild() # assign (a)'s left child to (b) "
print " b.insertLeft('d') # add left child (d) to (b)"
print " b.insertRight('e') # add right child (e) to (b)"
print
print ' a '
print ' / \ '
print ' b c # the Tree as of now'
print ' / \ '
print ' d e '
print
c = a.getRightChild()
c.insertLeft('f')
print " c = a.getRightChild() # assign (a)'s right child to (c) "
print " c.insertLeft('f') # add left child (f) to (c)"
print
print ' a '
print ' / \ '
print ' b c # the Tree as of now'
print ' / \ / '
print ' d e f '
print
print "-" * 70
print "a.getRightChild().getLeftChild().getRootVal()"
print a.getRightChild().getLeftChild().getRootVal()
print " " * 10, "is the same as"
print "c.getLeftChild().getRootVal()"
print c.getLeftChild().getRootVal()
print "-" * 70
print
Downloads
- the Class BinaryTree.py
- main program BinTre.py