class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
self.count = 1
class BST:
def __init__(self):
self.root = None
self.size = 0
def _insert(self,val,node):
if val<node.data:
if node.left:
self._insert(val,node.left)
else:
self.size+=1
node.left = Node(val)
elif val>node.data:
if node.right:
self._insert(val,node.right)
else:
self.size+=1
node.right = Node(val)
else:
self.size+=1
node.count+=1
def insert(self,val):
if not self.root:
self.size+=1
self.root = Node(val)
else:
self._insert(val,self.root)
def _inorder(self,node):
if node:
self._inorder(node.left)
self.bstview.append(node.data)
self._inorder(node.right)
def view(self):
if self.root:
self.bstview = []
self._inorder(self.root)
return self.bstview
def _min(self,node):
if node.left:
return self._min(node.left)
return node
def _max(self,node):
if node.right:
return self._max(node.right)
return node
def min(self):
if self.root:
return self._min(self.root).data
def max(self):
if self.root:
return self._max(self.root).data
def _remove(self,val,node):
if not node:
return
if val < node.data:
node.left = self._remove(val,node.left)
elif val > node.data:
node.right = self._remove(val,node.right)
else:
if node.count >1:
self.size-=1
node.count-=1
return node
elif not node.left:
temp = node.right
del node
self.size-=1
return temp
elif not node.right:
temp = node.left
del node
self.size-=1
return temp
else:
temp = self._min(node.right)
node.data = temp.data
node.right = self._remove(temp.data,node.right)
return node #WHY THIS IS NECESSARY PLEASE EXPLAIN!!
def remove(self,val):
if self.root:
self._remove(val,self.root)
b = BST()
for x in list(map(int,"20 10 30 5 15 25 35 3 7 23 27 40 4 45".split(" "))):
b.insert(x)
print(b.view())
print(b.min(),b.max(),b.size)
b.remove(20)
b.remove(45)
b.remove(1)
print(b.view())
print(b.min(),b.max(),b.size)
В приведенном выше коде BST, почему необходимо возвращать node в методе _remove()?Операторы if / elif уже возвращают узлы?
Кроме того, я был бы вам очень благодарен, если бы вы могли привести меня к простому / менее трудоемкому способу понимания рекурсивных функций (я знаю, что это такое и какони работают, мой вопрос: если кто-то спросит меня, как работает определенная рекурсивная функция, я смог бы объяснить его, не путая себя).