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 [EMAIL PROTECTED] Build and Release MontaVista Software -- http://mail.python.org/mailman/listinfo/python-list