if not node:
return node
Что означает этот код?
if not node.leftchild:
print('removing the node with single rightchild')
tempnode = node.rightchild
del node
return tempnode
При удалении элементов в дереве двоичного поиска при наличии одного дочернего элемента, если узел удален, дочерний элемент должен быть подключен к другому узлу.Однако я не понимаю, как это работает, потому что нет объявления, указывающего на другой узел.Как работает "tempnode" после возвращения?Я имею в виду, что после возврата нет использования, но я вижу, что если я возвращаю None или другое значение вместо tempnode, удаление не работает
Вот полная программа.
class Node:
def __init__(self,data):
self.data = data
self.leftchild = None
self.rightchild = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, data):
if not self.root:
self.root = Node(data)
else:
self.insert_node(data,self.root)
def insert_node(self,data, node):
if data < node.data:
if node.leftchild:
self.insert_node(data, node.leftchild)
else:
node.leftchild = Node(data)
else:
if node.rightchild:
self.insert_node(data, node.rightchild)
else:
node.rightchild = Node(data)
def remove(self, data):
if self.root:
self.root = self.remove_node(data, self.root)
def remove_node(self, data, node):
if not node:
return node
if data < node.data:
node.leftchild = self.remove_node(data, node.leftchild)
elif data > node.data:
node.rightchild = self.remove_node(data, node.rightchild)
else:
if not node.leftchild and not node.rightchild:
print('removing leaf node')
del node
return None
if not node.leftchild:
print('removing the node with single rightchild')
tempnode = node.rightchild
del node
return tempnode
elif not node.rightchild:
print('removing the node with single lefttchild')
tempnode = node.leftchild
del node
return tempnode
print('removing the node with two childs')
tempnode = self.get_predessor(node.leftchild)
node.data = tempnode.data
node.leftchild = self.remove_node(tempnode.data, node.leftchild)
return node
def get_predessor(self, node):
if node.rightchild:
return self.get_predessor(node.rightchild)
return node
def get_min_value(self):
if self.root:
return self.get_min(self.root)
def get_min(self, node):
if node.leftchild:
return self.get_min(node.leftchild)
return node.data
def get_max_value(self):
if self.root:
return self.get_max(self.root)
def get_max(self, node):
if node.rightchild:
return self.get_max(node.rightchild)
return node.data
def traverse(self):
if self.root:
self.traverse_in_order(self.root)
def traverse_in_order(self, node):
if node.leftchild:
self.traverse_in_order(node.leftchild)
print(node.data)
if node.rightchild:
self.traverse_in_order(node.rightchild)