Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
An binary tree sample implementation (insert, traverse_inorder, traverse_preorder, traverse_postorder included)
def binarytree(value):
return Node(value)
class Node(object):
def __init__(self, value):
self.__value = value
self.__left_node = None
self.__right_node = None
@property
def value(self):
return self.__value
@property
def left_node(self):
return self.__left_node
@property
def right_node(self):
return self.__right_node
def insert(self, value):
if value > self.__value:
if not self.__right_node:
self.__right_node = Node(value)
print('inserted {} to the right of {}'.format(value, self.__value))
else:
self.__right_node.insert(value)
else:
if not self.__left_node:
self.__left_node = Node(value)
print('inserted {} to the left of {}'.format(value, self.__value))
else:
self.__left_node.insert(value)
def traverse_inorder(self):
if self.__left_node:
self.__left_node.traverse_inorder()
print('node ', self.__value)
if self.__right_node:
self.__right_node.traverse_inorder()
def traverse_preorder(self):
print('node ', self.__value)
if self.__left_node:
self.__left_node.traverse_preorder()
if self.__right_node:
self.__right_node.traverse_preorder()
def traverse_postorder(self):
if self.__left_node:
self.__left_node.traverse_postorder()
if self.__right_node:
self.__right_node.traverse_postorder()
print('node ', self.__value)
def contains(self, value):
if value > self.__value:
if self.__right_node:
return self.__right_node.contains(value)
else:
return False
elif value < self.__value:
if self.__left_node:
return self.__left_node.contains(value)
else:
return False
else:
return True
def run():
print('------------inserting------------')
tree = binarytree(3)
tree.insert(5)
tree.insert(7)
tree.insert(4)
tree.insert(2)
tree.insert(1)
print('')
print('--------traversing in order------')
tree.traverse_inorder()
print('')
print('-------traversing pre order------')
tree.traverse_preorder()
print('')
print('------traversing post order------')
tree.traverse_postorder()
print('')
print('------contains------')
print(tree.contains(3))
print(tree.contains(1))
print(tree.contains(5))
print(tree.contains(7))
print(tree.contains(2))
print(tree.contains(4))
print(tree.contains(55))
print(tree.contains(6))
if __name__ == '__main__':
run()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment