how to construct a binary-tree using python?

[Carl J. Van Arsdall]

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
cvanarsdall at mvista.com
Build and Release
MontaVista Software