Pythonで学ぶ二分探索木

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None   # smaller values go left
        self.right = None  # larger values go right


def insert(node, value):
    if node is None:
        return Node(value)
    if value < node.value:
        node.left = insert(node.left, value)
    elif value > node.value:
        node.right = insert(node.right, value)
    return node


def contains(node, value):
    # Each comparison discards one whole subtree.
    while node is not None:
        if value == node.value:
            return True
        node = node.left if value < node.value else node.right
    return False


def inorder(node):
    # Left subtree, node, right subtree: visits values in sorted order.
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)


def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


root = None
for value in [50, 30, 70, 20, 40, 60, 80]:
    root = insert(root, value)

print("inorder:", inorder(root))
print("contains 60:", contains(root, 60))
print("contains 65:", contains(root, 65))
print("height:", height(root))