# A Binary Tree abstract data type
#
# Written by Eric Martin for COMP9021
class BinaryTree:
def __init__(self, value = None):
self.value = value
if self.value != None:
self.left_node = BinaryTree()
self.right_node = BinaryTree()
else:
self.left_node = None
self.right_node = None
def height(self):
if self.value == None:
return 0
return max(self._height(self.left_node), self._height(self.right_node))
# Both an empty tree and a tree consisting of its root are of height 0.
def _height(self, node):
if node.value == None:
return 0
return 1 + max(self._height(node.left_node), self._height(node.right_node))
# Number of values stored in tree.
def size(self):
if self.value == None:
return 0
return 1 + self.left_node.size() + self.right_node.size()
def occurs_in_tree(self, value):
if self.value == None:
return False
if self.value == value:
return True
return self.left_node.occurs_in_tree(value) or self.right_node.occurs_in_tree(value)
# Binary search for value.
def occurs_in_bst(self, value):
if self.value == None:
return False
if self.value == value:
return True
if value < self.value:
return self.left_node.occurs_in_bst(value)
return self.right_node.occurs_in_bst(value)
def is_bst(self):
if self.value == None:
return True
node = self.left_node
if node.value != None:
while node.right_node.value != None:
node = node.right_node
if self.value <= node.value:
return False
node = self.right_node
if node.value:
while node.left_node.value != None:
node = node.left_node
if node.value != None and self.value >= node.value:
return False
return self.left_node.is_bst() and self.right_node.is_bst()
# Inserts value in binary search and returns True in case value is not already in the tree.
# Otherwise, returns False.
def insert_in_bst(self, value):
if self.value == None:
self.value = value
self.left_node = BinaryTree()
self.right_node = BinaryTree()
return True
if self.value == value:
return False
if value < self.value:
return self.left_node.insert_in_bst(value)
return self.right_node.insert_in_bst(value)
# Deletes value from binary search and returns True in case value is stored in the tree.
# Otherwise, returns False.
def delete_in_bst(self, value):
return self._delete_in_bst(value, self, '')
def _delete_in_bst(self, value, parent, link):
if self.value == None:
return False
if value < self.value:
return self.left_node._delete_in_bst(value, self, 'L')
if value > self.value:
return self.right_node._delete_in_bst(value, self, 'R')
if self.left_node.value == None:
new_tree = self.right_node
elif self.right_node.value == None:
new_tree = self.left_node
elif self.left_node.right_node.value == None:
new_tree = self.left_node
new_tree.right_node = self.right_node
else:
node_1 = self.left_node
node_2 = node_1.right_node
while node_2.right_node.value != None:
node_1 = node_2
node_2 = node_2.right_node
new_tree = node_2
new_tree.right_node = self.right_node
node_1.right_node = node_2.left_node
new_tree.left_node = self.left_node
if link == '':
self.value = new_tree.value
self.left_node = new_tree.left_node
self.right_node = new_tree.right_node
elif link == 'L':
parent.left_node = new_tree
else:
parent.right_node = new_tree
return True
def print_binary_tree(self):
if self.value == None:
return
self._print_binary_tree(0, self.height())
def _print_binary_tree(self, n, height):
if n > height:
return
if self.value == None:
print('\n' * (2 ** (height - n + 1) - 1), end = '')
else:
self.left_node._print_binary_tree(n + 1, height)
print('\t' * n, self.value, sep = '')
self.right_node._print_binary_tree(n + 1, height)
def pre_order_traversal(self):
if self.value == None:
return []
values = [self.value]
values.extend(self.left_node.pre_order_traversal())
values.extend(self.right_node.pre_order_traversal())
return values
def in_order_traversal(self):
if self.value == None:
return []
values = self.left_node.in_order_traversal()
values.append(self.value)
values.extend(self.right_node.in_order_traversal())
return values
def post_order_traversal(self):
if self.value == None:
return []
values = self.left_node.post_order_traversal()
values.extend(self.right_node.post_order_traversal())
values.append(self.value)
return values
if __name__ == '__main__':
print('Testing empty tree:')
t = BinaryTree()
print(t.height())
print(t.size())
print(t.is_bst())
print(t.occurs_in_tree(0))
print(t.occurs_in_bst(0))
t.print_binary_tree()
print(t.pre_order_traversal())
print(t.in_order_traversal())
print(t.post_order_traversal())
print('\nTesting 1 node tree:')
t = BinaryTree(1)
print(t.height())
print(t.size())
print(t.is_bst())
print(t.occurs_in_tree(0))
print(t.occurs_in_bst(0))
print(t.occurs_in_tree(1))
print(t.occurs_in_bst(1))
t.print_binary_tree()
print(t.pre_order_traversal())
print(t.in_order_traversal())
print(t.post_order_traversal())
print('\nTesting a tree storing 1, 2, 3, 4, 5 and 6 twice:')
t = BinaryTree(3)
t_1 = BinaryTree(2)
t_2 = BinaryTree(5)
t_3 = BinaryTree(1)
t_4 = BinaryTree(4)
t_5 = BinaryTree(6)
t_6 = BinaryTree(6)
t.left_node = t_1
t.right_node = t_2
t_1.left_node = t_3
t_2.left_node = t_4
t_2.right_node = t_5
t_4.right_node = t_6
print(t.height())
print(t.size())
print(t.is_bst())
print(t.occurs_in_tree(0))
print(t.occurs_in_tree(1))
t.print_binary_tree()
print(t.pre_order_traversal())
print(t.in_order_traversal())
print(t.post_order_traversal())
print('\nTesting a binary tree:')
t = BinaryTree()
t.insert_in_bst(4)
t.print_binary_tree()
t.insert_in_bst(2)
t.print_binary_tree()
t.insert_in_bst(1)
t.print_binary_tree()
t.insert_in_bst(5)
t.print_binary_tree()
t.insert_in_bst(3)
t.print_binary_tree()
t.insert_in_bst(6)
t.print_binary_tree()
t.insert_in_bst(7)
t.print_binary_tree()
print(t.is_bst())
print(t.occurs_in_tree(3))
print(t.occurs_in_bst(3))
print(t.occurs_in_tree(8))
print(t.occurs_in_bst(8))
print(t.pre_order_traversal())
print(t.in_order_traversal())
print(t.post_order_traversal())
t.delete_in_bst(5)
t.print_binary_tree()
t.delete_in_bst(7)
t.print_binary_tree()
t.delete_in_bst(2)
t.print_binary_tree()
t.delete_in_bst(4)
t.print_binary_tree()
t.delete_in_bst(1)
t.print_binary_tree()
t.delete_in_bst(6)
t.print_binary_tree()
t.delete_in_bst(3)
t.print_binary_tree()
Resource created Thursday 08 October 2015, 12:05:04 AM.
file: binary_tree.py