Ответ Майкла объясняет, как вы, вероятно, должны были подойти к проблеме, но он не объяснил, что было не так с вашей текущей попыткой. Насколько я понимаю, ваша стратегия заключалась в том, чтобы исследовать каждый узел и отслеживать самое низкое значение, когда вы идете, используя рекурсию, чтобы найти все узлы. После того как вы изучили все узлы, вы знаете, что результат является минимальным для всего дерева. Это совершенно правильный подход, и он бы сработал, за исключением того, что аргументы не совсем работают так, как вы ожидаете.
Python передает аргументы по значению, а не по ссылке. Когда вы назначаете значение min_t, используя «min_t = root.key», он действует только внутри функции. Вызывающая функция не видит нового значения.
Вы можете проверить это с каким-то более простым кодом:
def add_one_to(x):
x = x + 1
print "add_one_to", x
x = 2
add_one_to(x)
print x
Вы можете увидеть при запуске коды, х увеличивались внутри функции, но не на верхнем уровне.
Это также применяется, когда функция вызывает себя. Каждый вызов имеет свой собственный набор локальных переменных, а присвоение локальной переменной внутри функции не влияет на вызывающий ее экземпляр.
Обратите внимание, что некоторые языки позволяют передавать аргументы по ссылке. Если вы передадите аргумент по ссылке, то назначение этого аргумента внутри функции также повлияет на вызывающего. Если Python был одним из этих языков, вы можете сделать min_t ссылочным аргументом, и ваша функция будет работать правильно.
Хотя Python не поддерживает опорные аргументы напрямую, вы можете также думать о ссылочном аргументе как значение, которое входит в функцию при ее вызове, а также передается обратно вызывающему абоненту, когда функция завершается. Вы можете делать обе эти вещи отдельно. Чтобы передать значение обратно вызывающему, верните это значение. Затем вызывающий может назначить эту функцию своему локальному, и вы в основном передали аргумент по ссылке.
Вот как вы могли бы применить, что к приведенному выше примеру:
def add_one_to(x):
x = x + 1
print "add_one_to", x
return x
x = 2
x = add_one_to(x)
print x
Просто добавьте возвращаемое значение и назначение, и она работает как положено.
Вы также можете применить это к исходной функции:
def min(root, min_t): # min_t is the initially the value of root
if not root:
return min_t
if root.key < min_t:
min_t = root.key
min_t = min(root.left, min_t)
min_t = min(root.right, min_t)
return min_t
Все, что я сделал, было добавить «MIN_T =» перед каждым вызовом мин() и изменить оператор возврата для возврата MIN_T в конце. (Я думаю, вы, вероятно, хотели бы вернуть min_t в любом случае. Min - это имя вашей функции, поэтому это не имело бы большого смысла.) Я считаю, что версия будет работать.
Редактировать: причина, по которой работает ваша функция min_tree, несмотря на все это, состоит в том, что n является списком, а списки являются изменяемыми объектами. Когда я говорил о «значениях» выше, я действительно имел в виду «объект». Каждое имя переменной в python сопоставляется с определенным объектом. Если у вас есть такой код:
def replace_list(x):
x = [1, 2, 3]
x = [2]
replace_list(x)
print x
В результате [2]. Итак, если вы присвоите новое значение x с помощью «x =», вызывающий не увидит его. Однако, если вы это сделаете:
def replace_list(x):
x.append(1)
x = [2]
replace_list(x)
print x
В результате получается [2, 1].Это связано с тем, что вы не изменили значение x; x по-прежнему указывает на тот же список. Однако этот список теперь содержит дополнительное значение. К сожалению, оператор «+ =» вводит в заблуждение. Вы можете подумать, что «x + = y» совпадает с «x = x + y», но в Python это не всегда так. Если «x» - это объект, который поддерживает «+ =», то эта операция будет модифицировать объект на месте. В противном случае он будет таким же, как «x = x + 1». Списки знают, что делать с «+ =», поэтому использование + = со списком изменит его на месте, но использовать его с номером не будет.
Вы действительно можете проверить это, не делая каких-либо вызовов функций:
x = [1, 2]
y = x
y += [3]
print x # [1, 2, 3]
print y # [1, 2, 3]
print x is y # True, x and y are the same object, which was modified in place
x = [1, 2]
y = x
y = y + [3]
print x # [1, 2]
print y # [1, 2, 3]
print x is y # False, y is a new object equal to x + [3]
x = 1
y = x
y += 2
print x # 1
print y # 3
print x is y # False, y is a new object equal to x + 2
Если это домашнее задание, пожалуйста, пометить его как таковой. Благодаря! – senderle
Это домашнее задание? – dckrooney
Нет! Редакция! – isal