Ответ 1
В рекурсивных строках вы ничего не возвращаете. Если вы хотите, чтобы он возвращал 0, вы должны заменить их такими строками, как:
return self.insert(key, root=tmp.left)
вместо
self.insert(key, root=tmp.left)
Я новичок в Python и рекурсивных функциях в целом, поэтому прошу простить мое невежество.
Я пытаюсь реализовать двоичное дерево поиска в Python и иметь следующий метод вставки (взятый из класса):
def insert(self, key, root=None):
'''Inserts a node in the tree'''
if root == None:
root = self.root
if root.key == None:
self._update(root, key)
return 0
else:
tmp = root
if key > tmp.key: # we work with the right subtree
self.insert(key, root=tmp.right)
elif key < tmp.key: # we work with the left subtree
self.insert(key, root=tmp.left)
else: # key already exists
return 0
Я не уверен, что это разборчиво, но оно проходит дерево до тех пор, пока оно не достигнет значения None и обновит node с помощью ключа для вставки.
Теперь этот метод работает красиво и правильно создает BST с нуля. Но есть проблема с операторами return, поскольку он возвращает только 0, если рекурсия не выполняется.
>>> bst.insert(10)
0
>>> bst.insert(15)
>>> bst.root.right.key
15
>>>
"Вставка" корневого ключа снова возвращает 0 (из строки 15), как это должно быть.
>>> bst.insert(10)
0
Я не могу понять, почему это происходит. Если я поставлю оператор печати в строке 6, он будет выполняться правильно, но он просто не вернет ничего после первой вставки. Почему это? (Я уверен, что у меня отсутствует основная информация о Python и рекурсии)
Спасибо за вашу помощь,
Иван
P.S.: Я читал, что рекурсия - это не лучший способ реализовать BST, поэтому я рассмотрю другие решения, но я хотел бы знать ответ на этот вопрос, прежде чем двигаться дальше.
В рекурсивных строках вы ничего не возвращаете. Если вы хотите, чтобы он возвращал 0, вы должны заменить их такими строками, как:
return self.insert(key, root=tmp.left)
вместо
self.insert(key, root=tmp.left)
Вы находитесь внутри функции и хотите вернуть значение, что вы делаете? Вы пишете
def function():
return value
В вашем случае вы хотите вернуть значение, возвращаемое вызовом функции, поэтому вам нужно сделать.
def function():
return another_function()
Однако вы делаете
def function():
another_function()
Почему вы думаете, что это должно сработать? Конечно, вы используете рекурсию, но в таком случае вы должны помнить Zen of Python, который просто говорит:
Особые случаи не являются достаточно сложными, чтобы нарушать правила.