学步园

class BST:
    def __init__(self):
        self.root = None

    def insert(self,x):
        if self.root == None:
            self.root = Node(x)
        elif self.root.data > x:
            self.root.left = self.root.left.insert(x)
        elif self.root.data < x:
            self.root.right = self.root.right.insert(x)
        else:
            return

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

    def lookup(self,x):
        if self.root == None:
            return False
        if self.root.data == x:
            return True
        elif self.root.data > x:
            return self.root.left.lookup(x)
        else:
            return self.root.right.lookup(x)

class Node:
    def __init__(self,data = None,left = None,right = None):
        self.data, self.left, self.right = data, left, right

写完过后 发觉了很大个问题

elif self.root.data > x:
            return self.root.left.lookup(x)
        else:
            return self.root.right.lookup(x)

在这两句里面root为None是就出现错误想来想去也没有想到方法，最后在programming python 里面找到了一种方法，就是把空节点抽象出来，而不是使用None

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):
        return False
    def insert(self,value):
        return BinaryNode(self,value,self)


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.right.lookup(value)
        elif self.data > value:
            return self.left.lookup(value)
    def insert(self,value):
        if self.data > value:
            self.left = self.left.insert(value)
        elif self.data < value:
            self.right = self.right.insert(value)
        return self
    def __repr__(self):
        return ('(%s, %s, %s )' %
                (repr(self.left), repr(self.data), repr(self.right)))