how to construct a binary-tree using python?

[hankssong]

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

[Carl J. Van Arsdall]

Re: how to construct a binary-tree using python?

hankssong wrote:[color=blue]
> 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.
>
>[/color]
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(inputD ata) #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.build Tag <= root.bTag:
if root.left == None:
root.left = self.addNode(in putData) #left is empty? add
else:
self.insertNode (inputData, root.left) #visit the left subtree
else:
if root.right == None:
root.right = self.addNode(in putData)
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(n odeToFind, root.left) )
else:
return( self.findNode(n odeToFind, root.right) )




--

Carl J. Van Arsdall
cvanarsdall@mvi sta.com
Build and Release
MontaVista Software

[vdrab]

Re: how to construct a binary-tree using python?

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.
[color=blue][color=green][color=darkred]
>>> x = ((2,4),(5,6))
>>> y, _ = x
>>> y[/color][/color][/color]
(2, 4)[color=blue][color=green][color=darkred]
>>> (_,y), _ = x
>>> y[/color][/color][/color]
4[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

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

[hankssong]

Re: how to construct a binary-tree using python?

I use google and get some detailed info in the page:

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/286239

Carl J. Van Arsdall ,vdrab, thank for your help!

[Antoon Pardon]

Re: how to construct a binary-tree using python?

Op 2006-05-06, hankssong schreef <songyi012133@g mail.com>:[color=blue]
> 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.[/color]

You may have a look here:

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

--
Antoon Pardon