BinarySearchTree
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
class Node():
def __init__(self, value):
self.value = value
self.right = None
self.left = None
class BinarySearchTree():
def __init__(self, root_value):
root = Node(root_value)
self.root = root
def insert(self, value):
curr_node = self.root
new_node = Node(value)
while(1):
if value > curr_node.value:
# print("go right")
if curr_node.right == None:
curr_node.right = new_node
break
else:
curr_node = curr_node.right
elif value < curr_node.value:
# print("go left")
if curr_node.left == None:
curr_node.left = new_node
break
else:
curr_node = curr_node.left
else:
print("value is already in the tree")
return False
return True
def lookup(self, value):
# return Node or None
curr_node = self.root
while(curr_node != None):
if value > curr_node.value:
curr_node = curr_node.right
elif value < curr_node.value:
curr_node = curr_node.left
else:
return curr_node
return curr_node
print("Hello World!")
tree = BinarySearchTree(9)
tree.insert(4)
assert(tree.insert(4) == False)
tree.insert(20)
tree.insert(1)
tree.insert(6)
tree.insert(15)
tree.insert(170)
assert((tree.lookup(170).value) == 170)
assert((tree.lookup(4).value) == 4)
assert((tree.lookup(20).value) == 20)
assert(tree.lookup(11) == None)
assert((tree.lookup(1).value) == 1)
assert((tree.lookup(6).value) == 6)
assert((tree.lookup(15).value) == 15)
assert((tree.lookup(9).value) == 9)
print("Goodbye Cruel World")
Python
INFO