hankssong wrote:
Hi everyone, I'm wondering whether it's possible to construct a
binary-tree using python.
Since python don't have pointer, it can't dynamically allocate memory
like C language.
But some important data structures like linked list, binary-tree and
hash table are closely linked with dynamic memory technology.
Its actually very possible to construct a binary tree in python. If you
do some googles searches you'll, in fact find, some implementations.
Its important to remember that python can dynamically make objects on
the fly. Objects are created as references and so you can make tree
nodes whenever you want to
Here are some snippets, I'm not the most advanced coder but its just to
show you that it can be done.
I wouldn't use this code verbatim, its taylored to a project I was doing
at the time, but I hope this helps you get an idea.
class TreeNode:
def __init__(self, nodeData):
self.left = None
self.right = None
[snip - stuff for my project]
class Tree:
def __init__(self):
self.root = None
#assigns the data to a new TreeNode
def addNode(self, inputData):
return TreeNode(inputData) #insert is recursive, so when it reaches
its ending point this is called
#this function traverses the tree and finds the spot to add the node
def insertNode(self, inputData, root):
def insertNode(self, inputData, root):
if inputData.buildTag <= root.bTag:
if root.left == None:
root.left = self.addNode(inputData) #left is empty? add
else:
self.insertNode(inputData, root.left) #visit the left subtree
else:
if root.right == None:
root.right = self.addNode(inputData)
else:
self.insertNode(inputData, root.right)
return #root
def findNode(self, nodeToFind, root): #nodeToFind is just a buildTag
string
if root == None:
return None
else:
#btag is something i needed for what I was doing, ignore it
#print "Comparing " + nodeToFind + " and " + root.bTag
if nodeToFind == root.bTag:
return root
elif nodeToFind < root.bTag:
return( self.findNode(nodeToFind, root.left) )
else:
return( self.findNode(nodeToFind, root.right) )
--
Carl J. Van Arsdall
cv*********@mvista.com
Build and Release
MontaVista Software
