用Python实现二叉搜索树

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

class BinarySearchTree(object):
    def __init__(self):
        self.root = None

    def insert(self, data):
        new_node = Node(data)
        if self.root is None:
            self.root = new_node
        else:
            curr_node = self.root
            while curr_node is not None:
                if data < curr_node.data:
                    if curr_node.left is None:
                        curr_node.left = new_node
                        break
                    else:
                        curr_node = curr_node.left
                else:
                    if curr_node.right is None:
                        curr_node.right = new_node
                        break
                    else:
                        curr_node = curr_node.right

    def search(self, data):
        curr_node = self.root
        while curr_node is not None:
            if curr_node.data == data:
                return True
            elif data < curr_node.data:
                curr_node = curr_node.left
            else:
                curr_node = curr_node.right
        return False

    def inorder_traversal(self, curr_node, traversal):
        if curr_node is not None:
            self.inorder_traversal(curr_node.left, traversal)
            traversal.append(curr_node.data)
            self.inorder_traversal(curr_node.right, traversal)
        return traversal

bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

print(bst.search(20)) # True
print(bst.search(90)) # False

inorder_list = bst.inorder_traversal(bst.root, [])
print(inorder_list) # [20, 30, 40, 50, 60, 70, 80]