
xxxxxxxxxx
#Binary Search Tree Implementation - www.101computing.net/binary-search-tree-implementation/
import os
from tree import drawTree
#A class to implement a Node / Binary Search Tree
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def draw(self):
drawTree(self)
#Binary Search
def find(self, value):
node=self
while node:
if value < node.val:
node = node.left
elif value > node.val:
node = node.right
else:
return node
#Return the smallest (most left) value of the BST
def min(self):
node=self
while node and node.left:
node = node.left
return node
#Return the largest (most right) value of the BST
def max(self):
node=self
while node and node.right:
node = node.right
return node
def preorder_traversal(self):
self.__listOfNodes = []
self.__preorderTraversal(self)
print(self.__listOfNodes)
def inorder_traversal(self):
self.__listOfNodes = []
self.__inorderTraversal(self)
print(self.__listOfNodes)
def postorder_traversal(self):
self.__listOfNodes = []
self.__postorderTraversal(self)
print(self.__listOfNodes)
#Pre-Order Traversal of the Binary Search Tree
def __preorderTraversal(self, node):
if node!=None:
self.__listOfNodes.append(node.value)
self.__preorderTraversal(node.left)
self.__preorderTraversal(node.right)
#In-Order Traversal of the Binary Search Tree
def __inorderTraversal(self, node):
if node!=None:
self.__inorderTraversal(node.left)
self.__listOfNodes.append(node.value)
self.__inorderTraversal(node.right)
#Post-Order Traversal of the Binary Search Tree
def __postorderTraversal(self, node):
if node!=None:
self.__postorderTraversal(node.right)
self.__postorderTraversal(node.left)
self.__listOfNodes.append(node.value)
#Insert value into node by following BST properties
def insert(self, value, node=None, root=True):
if root:
node=self
if node is None:
return Node(value)
if value < node.value:
node.left = self.insert(value, node.left, False)
elif value > node.value:
node.right = self.insert(value, node.right, False)
else:
#Duplicate value, ignore it
return node
return node
#Deletes node from the tree. Return a pointer to the resulting tree
def delete(self, value, node=None, root=True):
if root:
node=self
if node is None:
return None
if value < node.value:
node.left = self.delete(value, node.left, False)
elif value > node.value:
node.right = self.delete(value, node.right, False)
elif node.left and node.right:
tmp_cell = self.min(node.right)
node.val = tmp_cell.value
node.right = self.delete(node.value, node.right, False)
else:
if node.left is None:
node = node.right
elif node.right is None:
node = node.left
def convert(value,dataType):
if dataType=="1":
return int(value)
elif dataType=="2":
return float(value)
else:
return str(value)
#########################################################################
print("How would you like to sort your data:")
print(" - By numerical order (integers only).")
print(" - By numerical order (floats).")
print(" - By alphabetical order.")
dataType = input("Your choice: (1, 2 or 3):")
value = input("Enter the first value (root) of your Binary Search Tree:")
value = convert(value,dataType)
tree = Node(value)
while True:
os.system('clear')
tree.insert(value)
print("Your Binary Search Tree so far:")
tree.draw()
print("")
print("In-order traversal:")
tree.inorder_traversal()
print("")
print("Pre-order traversal:")
tree.preorder_traversal()
print("")
print("Post-order traversal:")
tree.postorder_traversal()
print("")
value = input("Enter a new value or exit to quit...:")
if value=="exit":
break
else:
value=convert(value,dataType)
task_alt