binary tree in python?
Hrvoje Niksic
hniksic at arsdigita.com
Mon Nov 6 08:24:46 EST 2000
ranga_r at my-deja.com writes:
> i would like to know if there is any reference/documentation/code
> available on implementing a binary tree in python.
Here is a nice binary tree implementation by Tim Peters. You can save
it to a file named `bintree.py' and do things like:
import bintree
tree = bintree.BinaryTree()
tree.insert('foo')
tree.insert('bar')
tree.insert('baz')
tree.insert('ahoy there!')
print tree.inorder()
['ahoy there!', 'bar', 'baz', 'foo']
# bintree.py
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, val):
root = self.root
lastdir = None
while root:
lastroot = root
if val <= root.val:
lastdir = 'left'
root = root.left
else:
lastdir = 'right'
root = root.right
new = Node(val)
if lastdir is None:
self.root = new
elif lastdir == 'left':
lastroot.left = new
else:
lastroot.right = new
def inorder(self):
result = []
self.__helper(self.root, result)
return result
def __helper(self, root, result):
if root is not None:
self.__helper(root.left, result)
result.append(root.val)
self.__helper(root.right, result)
More information about the Python-list
mailing list