-
Notifications
You must be signed in to change notification settings - Fork 0
/
task4.py
109 lines (80 loc) · 3.56 KB
/
task4.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#Name: Russell Sammut-Bonnici
#ID: 0426299(M)
#Task: 4
#class concerned with initialising node
class Node:
#initializes node
def __init__(self, value=None):
self.value = value
self.leftChild = None
self.rightChild = None
#class concerned with Binary Search Tree functions
class BinarySearchTree:
#initializes tree
def __init__(self):
self.root = None
#inserts node into the tree, calls _insertNode after root is set
def insertNode(self, value):
if self.root == None:
self.root = Node(value)
else:
self._insertNode(value, self.root)
#recursive function called for inserting node after root
def _insertNode(self, value, currNode):
#when the value is less than its previous
if value < currNode.value:
#if left child doesn't exist add as left, else add under left
if currNode.leftChild == None:
currNode.leftChild = Node(value)
else:
self._insertNode(value, currNode.leftChild)
#when the value is more than its previous
elif value > currNode.value:
#if right child doesn't exist add as right, else add under right
if currNode.rightChild == None:
currNode.rightChild = Node(value)
else:
self._insertNode(value, currNode.rightChild)
#when the value is equal to its previous
else:
print "Error: Inserted value %d is already in the Binary Search Tree therefore it wasn't inserted."%currNode.value
return -1
#prints the tree with all its contained nodes
def printTree(self):
#prints tree when root is not null with recursive function call
if self.root!=None:
self._printTree(self.root)
else:
print("Error: Tree does not have any nodes to print out")
return -1
#recursive function called for printing nodes left to right
def _printTree(self,currNode):
#base case is when the bottom of the tree is reached (when node==None)
if currNode!=None:
self._printTree(currNode.leftChild) #goes to the deepest node on the left
# prints when left and right child don't exist
if(currNode.leftChild==None and currNode.rightChild==None):
print("[ %s ] ---> \tLEFT: [%s] \tRIGHT: [%s]" % (currNode.value, currNode.leftChild, currNode.rightChild))
# prints when left child only doesn't exist
elif(currNode.leftChild==None):
print("[ %s ] ---> \tLEFT: [%s] \tRIGHT: [ %s ]" % (currNode.value, currNode.leftChild, currNode.rightChild.value))
# prints when right child only doesn't exist
elif(currNode.rightChild==None):
print("[ %s ] ---> \tLEFT: [ %s ] \tRIGHT: [%s]" % (currNode.value, currNode.leftChild.value, currNode.rightChild))
# prints when left and right child do exist
else:
print("[ %s ] ---> \tLEFT: [ %s ] \tRIGHT: [ %s ]" % (currNode.value, currNode.leftChild.value, currNode.rightChild.value))
self._printTree(currNode.rightChild) #goes to the node right from the left, then up a level
bst = BinarySearchTree() #initializing instance of class
#incrementally building up bst with a sequence of integers
bst.insertNode(8)
bst.insertNode(6)
bst.insertNode(9)
bst.insertNode(1)
bst.insertNode(3)
bst.insertNode(2)
bst.insertNode(4)
bst.insertNode(5)
bst.insertNode(10)
print("The Binary Search Tree's nodes from left to right are:")
bst.printTree()