471,071 Members | 1,516 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,071 software developers and data experts.

how to construct a binary-tree using python?

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.

Any help that can be provided would be greatly appreciated.

Thanks in advance

May 6 '06 #1
4 23932
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

May 6 '06 #2
Depending on what concrete use you have for binary trees, you may want
to consider tuples. What's cool about them is that you get pattern
matching on your tree for free.
x = ((2,4),(5,6))
y, _ = x
y (2, 4) (_,y), _ = x
y 4


Or you could code your own binary tree class subclassing tuple.
.... just a thought.
v.

May 6 '06 #3
I use google and get some detailed info in the page:
http://aspn.activestate.com/ASPN/Coo.../Recipe/286239
Carl J. Van Arsdall ,vdrab, thank for your help!

May 6 '06 #4
Op 2006-05-06, hankssong schreef <so**********@gmail.com>:
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.

Any help that can be provided would be greatly appreciated.


You may have a look here:

http://www.pardon-sleeuwaegen.be/antoon/avltree.html

--
Antoon Pardon
May 10 '06 #5

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

1 post views Thread by Steven Arnold | last post: by
9 posts views Thread by Maurizio Penna | last post: by
11 posts views Thread by Charles T. | last post: by
18 posts views Thread by Bern | last post: by
5 posts views Thread by Luke Vogel | last post: by
2 posts views Thread by Steven T. Hatton | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.