Python возвращает элемент из рекурсивной DFS

Question

Это относится к тому, как Python передается по ссылке или по значению в зависимости от того, является ли объект неизменным или нет. Я могу рекурсивно пройти через двоичное дерево и распечатать все значения, но это немного сложнее, если я хочу вместо этого вернуть определенный элемент. В приведенном ниже коде я (дважды) пытаюсь вернуть узел, если его атрибут данных соответствует переданному целому числу. N1 и n2 - это значения типа int.

def get_node(self, d, root, n=[]):
    if (root == None):
        return
    else:
        if(root.data == d):
            n.append(root)
        self.get_node(d,root.left)
        self.get_node(d, root.right)
        return n



def tree_traversal(self, n1, n2):
    n1 = self.get_node(n1,self.root)[0]
    n2 = self.get_node(n2,self.root)[1]
    print(n1.data)
    print(n2.data)
    return self.helper(n1,n2)

Это работает, и я получаю список, который содержит объекты узлов, которые я ищу. Однако, если вместо возврата (и передачи в качестве аргумента) списка, я использую строку или объект None для последующего изменения, это не сработает. Я предполагаю, что это потому, что списки изменчивы, а строки нет. Более того, вы увидите, что я должен назначить n [1] для n2, потому что по какой-то причине даже после выхода из рекурсивного вызова get_node и повторного выполнения для n2 возвращаемый список по-прежнему содержит n1 в 0-м индексе.

Может кто-нибудь объяснить, почему список все еще изменяется при назначении на n2? И есть ли способ вместо передачи в качестве аргумента и возврата пустого списка n, передачи в качестве аргумента и возврата обычного объекта со значением по умолчанию None?

Answer 1

Ваша первая проблема заключается в следующем:

def get_node(self, d, root, n=[]):

Существует множество предупреждений о том, что вы не можете использовать изменяемые данные для задания аргумента по умолчанию. Мы не говорим о передаче по ссылке или передаче по значению здесь (Python только передает значение - он передает указатели на контейнеры по значению - передача по ссылке - это совсем другое . Проблема здесь в том, что значение по умолчанию оценивается только один раз, поэтому all последующие вызовы будут использовать такую ​​же структуру. почему ты:

нужно присвоить n [1] n2, потому что по какой-то причине, даже после выход из рекурсивного вызова get_node и повторение n2, возвращенный список все еще содержит n1 в 0-м индексе

Теперь вы знаете причину. Это почти идентично использованию глобального для хранения результатов во время вашей рекурсии. Избегайте этого.

Ваши функции, похоже, не разработаны должным образом. Если мы работаем с деревом, то мы должны иметь возможность делать get_node() или tree_traversal() в любой точке дерева, в коде не должно быть фиксированных root. Кроме того, использование n1 и n2 разных типов и значений в одной и той же функции сбивает с толку - используйте разные имена переменных. Давайте попробуем это так:

class Node():
    def __init__(self, data, left=None, right=None):

        assert (data is not None), "Error in tree/model logic!"

        self.data = data
        self.left = left
        self.right = right

    def get_node(self, d):

        if self.data == d:
            return self

        if self.left is not None:
            result = self.left.get_node(d)
            if result is not None:
                return result

        if self.right is not None:
            result = self.right.get_node(d)
            if result is not None:
                return result

        return None

    def tree_traversal(self, n1, n2):
        node1 = self.get_node(n1)
        node2 = self.get_node(n2)

        return node1, node2

root = Node(0)
root.left = Node(1, Node(2), Node(3, Node(4)))
root.right = Node(5, Node(6), Node(7, Node(8), Node(9)))

print(root.tree_traversal(3, 9))

Теперь давайте обсудим, как это подходит или не подходит вашей модели.