Binary tree in Python

Python includes some excellent data structures like lists and dictionaries (hash tables). But you can also implement other traditional data structures, like a binary tree:

class treeNode: def __init__(self, data): self.data = data self.left = None self.right = None def add(self, node): if self.data == node.data: print "Node already exists" return if node.data < self.data: if self.left != None: self.left.add(node) else: self.left = node else: if self.right != None: self.right.add(node) else: self.right = node def desc(self): if self.left != None: self.left.desc() if self.data != None: print self.data if self.right != None: self.right.desc() class binaryTree: def __init__(self): self.root = None def add(self, data): node = treeNode(data) if self.root == None: self.root = node else: self.root.add(node) def desc(self): if self.root == None: print "Tree is empty" else: self.root.desc() class person: def __init__(self, name, age): self.name = name self.age = age def main(): tree = binaryTree() tree.add(53) tree.add(dict(x=4,y=2)) tree.add(33) tree.add(person('Spi', 28)) tree.add(dict(x=1,y=3)) tree.add(31) tree.add(person('Eneko', 30)) tree.add(dict(x=3,y=6)) tree.add(['San Luis Obispo','CA',93405]) tree.add(person('Fredi', 30)) tree.add(dict(x=1,y=2)) tree.add(35) tree.add(['Paso Robles','CA',93446]) tree.desc() if __name__ == "__main__" : main()

The code above will output this:

<__main__.person instance at 0x2a7418> <__main__.person instance at 0x2a74b8> <__main__.person instance at 0x2a7558> 31 33 35 53 {'y': 2, 'x': 1} {'y': 3, 'x': 1} {'y': 6, 'x': 3} {'y': 2, 'x': 4} ['Paso Robles', 'CA', 93446] ['San Luis Obispo', 'CA', 93405]

As you can see, the beauty resides in the fact that tree nodes can contain any kind of object. In this case I'm adding integer nodes, dictionaries, lists and even custom defined objects (person).

Comparing different type/class elements results on an interesting output. I don't quite understand why an integer is positioned before a list but after an object, but it is interesting to see this is a coherent behavior.

Finally you can also see how dictionaries are properly sorted, but the keys are not displayed in order. I guess this is the internal order the hash table actually has.

Enjoy!

Update:

Wow... I was just thinking how cool it would be to have a default method on all objects to return a string representation of themselves. I first learn about this excellent idea when learning Cocoa, where all objects have a method Description to display or print their content. Well, in order to do the same in Python the only thing we need to do is define the function __str__ in our class (found here):

class person: def __init__(self, name, age): self.name = name self.age = age def __str__(self): return 'Person %s (%d)' % (self.name, self.age)

Now, whenever we print a person object, the person's name and age will show up instead of the object memory address:

Person Spi (28) Person Eneko (30) Person Fredi (30)

Isn't that great?

Submitted by Eneko Alonso on Thu, 2008-04-24 20:21

Well, I remember from my

Submitted by BigFredi (not verified) on Fri, 2008-04-25 08:24.

Well, I remember from my experience with C++ (long, very long time ago) that you could overcharge operators. I remember I used to overcharge the ">>" operator and I remember I tried to overcharge the casting into char* in order to be able to print an object (Actually I don't remember if this worked, but at least I remember I tried with some results). It would be something similar.

Eneko Alonso

un Navarro en California

Projects

Recent comments

Feeds

Friends online

Binary tree in Python

Well, I remember from my

Post new comment