Home Original page

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