-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbst.py
151 lines (138 loc) · 4.66 KB
/
bst.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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
# Algorthms GUI Project / bst.py
# Created on: 07-Nov-2018
# Author: Gourav Siddhad
# Binary Search Tree
class BST_Node():
def __init__(self, data=None):
self.data = data
self.left = None
self.right = None
self.parent = None
class BST():
def __init__(self):
self.root = BST_Node(None)
self.total = 0
def read_File(self, inputFile):
with open(inputFile, 'r') as Input:
for line in Input:
ints = [int(x) for x in line.split()]
for v in ints:
self.insert(v)
def insert(self, new_value):
self.total = self.total + 1
self.insert_node(BST_Node(new_value))
def get_total(self):
return self.total
def insert_node(self, new_node, current_node=None):
if current_node is None:
current_node = self.root
if current_node.data:
if new_node.data < current_node.data:
if current_node.left is None:
new_node.parent = current_node
current_node.left = new_node
else:
self.insert_node(new_node, current_node.left)
else:
if current_node.right is None:
new_node.parent = current_node
current_node.right = new_node
else:
self.insert_node(new_node, current_node.right)
else:
current_node.data = new_node.data
current_node.left = new_node.left
current_node.right = new_node.right
current_node.parent = new_node.parent
def print_tree(self, current_node=None):
output = ''
if current_node is None:
current_node = self.root
stack = []
stack.append(current_node.left)
stack.append(current_node.right)
output = str(current_node.data) + ' '
while stack:
n = stack.pop(0)
if n is not None:
# print(n.data, end=' ')
output = output + str(n.data) + ' '
stack.append(n.left)
stack.append(n.right)
# else:
#print('Null', end=' ')
return output
def lookup(self, data, current_node=None):
if current_node is None:
current_node = self.root
if data < current_node.data:
if current_node.left is None:
return None
return self.lookup(data, current_node.left)
elif data > current_node.data:
if current_node.right is None:
return None
return self.lookup(data, current_node.right)
else:
return current_node
def children_count(self, current_node=None):
if current_node is None:
current_node = self.root
cnt = 0
if current_node.left:
cnt += 1
if current_node.right:
cnt += 1
return cnt
def delete(self, data):
# get node containing data
node = self.lookup(data)
if node is not None:
children_count = self.children_count(node)
else:
return 'Node Not Found'
parent = node.parent
if children_count == 0:
# if node has no children, just remove it
if parent:
if parent.left is node:
parent.left = None
else:
parent.right = None
del node
else:
self.root = BST_Node()
elif children_count == 1:
# if node has 1 child
# replace node with its child
if node.left:
n = node.left
else:
n = node.right
if parent:
if parent.left is node:
parent.left = n
else:
parent.right = n
del node
# if root node
else:
self.root.left = n.left
self.root.right = n.right
self.root.data = n.data
else:
# if node has 2 children
# find its successor
parent = node
successor = node.left
while successor.right:
parent = successor
successor = successor.right
# replace node data by its successor data
node.data = successor.data
# fix successor's parent's child
if parent.right == successor:
parent.right = successor.left
else:
parent.left = successor.left
return 'Node Deleted'