15: Binary Trees

Example 1: Page 306

In [1]:
class Node:
	def __init__(self):	#special method to create objects
	#with instances customized to a specific initial state
		self.iData = 0	#data item (key)
		self.dData = 0	#data item
		self.pLeftChild = None	#this node's left child
		self.pRightChild = None	#this node's right child

	def displayNode(self):	#display ourself
		print '{', self.iData, ',', self.dData, '}'
#	end class Node

Example 2: Page 307

In [2]:
class Node:
	def __init__(self):
		self._p1	#points to Person object
		self._pLeftChild	#points to left child
		self._pRightChild	#points to right child

Example 3: Page 307

In [1]:
class Tree:
	#as private instance variables don't exist in Python,
	#hence using a convention: name prefixed with an underscore, to treat them as non-public part
	def __init__(self):
		self._pRoot  = None	#first node of tree

	def find(self, key):	#find node with given key
		pass

#using Id as id reserved in Python
	def insert(self, Id, dd):	#insert new node
		pass

	def traverse(self, traverseType):
		pass

	def displayTree(self):
		pass
#end class Tree

Example 4: Page 310

In [4]:
def find(key):	#find node with given key
	#(assumes non-empty tree)
	pCurrent = pRoot	#start at root,
	while pCurrent.iData != key:	#while no match,
		if key < pCurrent.iData:	#go left?
			pCurrent = pCurrent.pLeftChild
		else:	#or go right?
			pCurrent = pCurrent.pRightChild
		if not pCurrent:	#if no child,
			return None#didn't find it
	return pCurrent	#found it
#end find

Example 5: Page 313

In [5]:
#using Id as id is reserved in Python
def insert(Id, dd):	#insert new node
	pNewNode = Node()	#make new node
	pNewNode.iData = Id#insert data
	pNewNode.dData = dd
	if not pRoot:	#no node in root
		pRoot = pNewNode
	else:	#root occupied
		pCurrent = pRoot	#start at root
		while True:	#(exits internally)
			pParent = pCurrent
			if Id < pCurrent.iData:	#go left?
				pCurrent = pCurrent.pLeftChild
				if not pCurrent:	#if end of the line,
					pParent.pLeftChild = pNewNode	#insert on left
					return
			else:	#or go right?
				pCurrent = pCurrent.pRightChild
				if not pCurrent:	#if end of the line
					pParent.pRightChild = pNewNode	#insert on right
					return
			#end else go right
	#end else not root
#end insert()