#python #binary-search-tree #nonetype #treenode
Вопрос:
У меня есть двоичное дерево поиска. Я написал основную вставку, удаление, обход всего дерева и нахожу его максимальный и минимальный узел дерева, но у меня возникают проблемы с поиском максимального и минимального узла после удаления минимального или максимального узла.
Эта функция удаляет определенный узел:
def deleteNode(self,val):
if self.data:
if self.data > val:
self.left.deleteNode(val)
elif self.data < val:
self.right.deleteNode(val)
else:
if self.left is None:
self.data = self.right
return True
elif self.right is None:
self.data = self.left
return True
else:
dltNode = self
dltNode.data = self.data
largest = self.left.findMax()
dltNode.data = largest
dltNode.left.deleteNode(largest)
return True
Эта функция находит минимальный узел:
def findMin(self):
if self.data:
if self.left is None:
return self.data
else:
return self.left.findMin()
И это для максимального узла:
def findMax(self):
if self.data:
if self.right is None:
return self.data
else:
return self.right.findMax()
Функции findMin и findMax прекрасно работают без удаления какого-либо узла.
Если я когда-нибудь позвоню, то после удаления минимального и максимального узла они не вернут ни одного, независимо от того, должны ли они возвращать только целочисленные данные узла. Вот скриншот моего вывода:
Он должен напечатать 34 вместо Ни одного.
Вот мой полный код
Ответ №1:
Есть несколько проблем в deleteNode
if self.data
не должно быть там: это означало бы, что вы не можете удалить узел со значением 0 из дерева. Аналогичная проблема существует и в других методах (findMin
,findMax
,insert
, …).self.left.deleteNode(val)
выполняется без предварительной проверки того, чтоself.left
нетNone
. То же самое верно и дляself.right.deleteNode(val)
self.data = self.right
присваивает ссылку на узелdata
атрибуту (который должен быть числом).- Функция иногда ничего не возвращает (
None
) илиTrue
. Из-за рекурсивной природы исходный вызывающий метод получитNone
. Это непоследовательно. - Функция не может справиться с удалением корневого узла, так как вызывающий будет продолжать использовать ссылку на корневой узел (
t
илиt2
в вашем примере кода).
Чтобы решить эти проблемы, вам следует либо создать отдельный Tree
класс, либо согласиться с тем, что deleteNode
возвращает корневой узел дерева, который может быть корнем, отличным от корня, на котором был сделан вызов (когда корневой узел был удален), или даже None
когда это был последний узел дерева.
Вот как это будет выглядеть:
def deleteNode(self,val):
if self.data > val:
if self.left:
self.left = self.left.deleteNode(val)
elif self.data < val:
if self.right:
self.right = self.right.deleteNode(val)
else:
if self.left is None:
return self.right
elif self.right is None:
return self.left
else:
largest = self.left.findMax()
self.data = largest
self.left = self.left.deleteNode(largest)
return self
Чтобы сделать это правильно, вам нужно будет использовать возвращаемое значение из этого метода, например:
t1 = t1.deleteNode(34)
NB: В некоторых методах вы проверяете, есть ли self.data is None
. Я понимаю, что это какое-то особое условие для указания на то, что корневой узел на самом деле не является узлом и должен рассматриваться как пустое дерево, но это не очень хороший шаблон. Вместо этого пустое дерево должно быть просто None
, или вы должны определить другой Tree
класс , у которого есть root
атрибут, который может быть None
.