二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

二叉查找树的特点则在于对于树中的每个节点X，它的左子树中所有项的值小于X中的项，而它的右子树中所有项的值大于X中的项。这意味着该树所有的元素都可以用某种一致的方式排序。如下图所示是一个二叉查找树：

为实现一个二叉查找树，我们将创建三个类：

BinaryTree：代表一个二叉树，实现初始化和操作；

EmptyNode：代表空节点；

BinaryNode：代表非空节点，具有一个值和两个子树。

实现代码如下：

class BinaryTree:
    def __init__(self):
        self.tree = EmptyNode()

    def __repr__(self):
        return repr(self.tree)

    def lookup(self, value):
        return self.tree.lookup(value)

    def insert(self, value):
        self.tree = self.tree.insert(value)


class EmptyNode:
    def __repr__(self):
        return '*'

    def lookup(self, value):                      # fail at the bottom
        return False

    def insert(self, value):
        return BinaryNode(self, value, self)      # add new node at bottom


class BinaryNode:
    def __init__(self, left, value, right):
        self.data, self.left, self.right  =  value, left, right

    def lookup(self, value):
        if self.data == value:
            return True
        elif self.data > value:
            return self.left.lookup(value)               # look in left
        else:
            return self.right.lookup(value)              # look in right

    def insert(self, value):
        if self.data > value:
            self.left = self.left.insert(value)          # grow in left
        elif self.data < value:
            self.right = self.right.insert(value)        # grow in right
        return self

    def __repr__(self):
        return ('( %s, %s, %s )' %
                 (repr(self.left), repr(self.data), repr(self.right)))

下面来创建之前图示中的二叉树：

>>> bt = BinaryTree()
>>> for i in [3, 1, 9, 2, 7]:
>>>    bt.insert(i)
>>> bt
( ( *, 1, ( *, 2, * ) ), 3, ( ( *, 7, * ), 9, * ) )

该实例来自于《Programming Python》4th Edition