Поиск минимального значения в двоичном дереве, Python

Ответ Майкла объясняет, как вы, вероятно, должны были подойти к проблеме, но он не объяснил, что было не так с вашей текущей попыткой. Насколько я понимаю, ваша стратегия заключалась в том, чтобы исследовать каждый узел и отслеживать самое низкое значение, когда вы идете, используя рекурсию, чтобы найти все узлы. После того как вы изучили все узлы, вы знаете, что результат является минимальным для всего дерева. Это совершенно правильный подход, и он бы сработал, за исключением того, что аргументы не совсем работают так, как вы ожидаете.

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 

Вы можете видеть, когда вы запускаете код, который 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 () и сменить оператор return для возврата 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 

Для этой конкретной задачи вы хотите пересечь все дерево и вернуть наименьшее значение. Но в целом основной принцип рекурсии состоит в том, что после этого вы снова вызываете функцию, вам предоставляется модифицированная версия той же проблемы.

Рассмотрим ваше дерево:

  root / \ left right 

Когда вы вызываете рекурсивную функцию в левом поддереве, вы снова получаете дерево. Таким образом, вы должны иметь возможность использовать такую ​​же логику.

Ключом для рекурсивной функции является базовый регистр и рекурсивный шаг. В примере с деревом базовый регистр не тогда, когда вы нашли минимальное значение (как бы вы знали?), А скорее, когда вы достигли дна дерева (он же лист).

И ваш рекурсивный шаг рассматривает каждую из вспомогательных проблем (bin_min (слева) и bin_min (справа)).

Последняя часть рассматривает возвращаемое значение. Инвариант заключается в том, что ваша функция вернула минимальный элемент, который он видел. Таким образом, когда ваш рекурсивный вызов возвращается, вы знаете, что это самый маленький элемент, а затем вещь, которую вам нужно вернуть, является наименьшим элементом из трех возможных вариантов (root, left_min и right_min).

 def min_bin(root): if not root: return MAX_VAL left_min = min_bin(root.left) right_min = min_bin(root.right) return min(left_min, right_min, root.val) 

Обратите внимание, что это другое решение, чем @Rik Poggi's. Он использует хвостовую рекурсию, чтобы немного ее оптимизировать.

Потому что вы получите больше от того, чтобы попытаться понять это самостоятельно, чем законченное решение, вот несколько советов. Прежде всего, вы не должны называть его min , потому что, конечно, вы не можете назвать min python, чтобы проверить свои результаты. И поскольку ответ Майкла напомнил мне, вам не нужно проходить в min_t потому что вместо этого вы можете протестировать root.key но я думаю, что это полезно для перехода в min_t чтобы понять проблему.

Кроме того, ваши первые строки в порядке; хорошо сделано здесь. :

 def tree_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 . Второй – это минимум right поддерева. И третий – это минимум left поддерева. Получите последние два значения (сюда входит рекурсивный вызов), а затем верните наименьшее значение.

Вот рекурсивный метод для нахождения минимального элемента:

 minelement = float("inf") def minimum(self, root): global minelement if root: if root.data < minelement: minelement = root.data self.minimum(root.left) self.minimum(root.right) return minelement