связанная структура python - вставка дочернего элемента в родительский узел A также вставляется в узел A

Я пытаюсь реализовать связанную структуру для дерева с помощью python, это выдержка из моего кода.

class Node(object):
    def __init__(self,value,father=None,children=[]):
        self.value=value
        self.father=father
        self.children=children
    def __str__(self):
        return self.value

class Tree(object):

    def __init__(self,root=None):
        self.root=root
    def insertNode(self,new_node,father_value):
        father_node=self.find_node(father_value)
        if not father_node:
            return False
        new_node.father=father_node
        print("Node's information BEFORE adding child to father's list of children")
        print(f"Father node (find) {father_node}")
        print(f"Father node's children {[x.value for x in father_node.children]}")
        print(f"New node's father {new_node.father}")
        print(f"New node's children {[x.value for x in new_node.children]}")
        father_node.children.append(new_node)
        print("Node's information AFTER adding child to father's list of children")
        print(f"Father node (find) {father_node}")
        print(f"Father node's children {[x.value for x in father_node.children]}")
        print(f"New node's father {new_node.father}")
        print(f"New node's children {[x.value for x in new_node.children]}")

    def find_node(self,value):
        stack=[self.root]
        while True:
            if len(stack)==0:
                return False
            node=stack.pop()
            if node.value==value:
                return node
            children=node.children
            stack.extend(children)

n1=Node("A")
tree=Tree(n1)
tree.insertNode(Node("B"),"A")

n1=Node("A")
tree=Tree(n1)
tree.insertNode(Node("B"),"A")

ВЫХОД

Node's information BEFORE adding child to father's list of children

Father node (find) A
Father node's children []
New node's father A
New node's children []
Node's information AFTER adding child to father's list of children
Father node (find) A
Father node's children ['B']
New node's father A
New node's children ['B']

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


python tree optional-parameters optional-arguments
person Ángel Santander    schedule 13.11.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Проблема возникает из-за того, как Python обрабатывает значения по умолчанию для необязательных параметров функции.

В class Node(object) у вас есть эта строка:

def __init__(self,value,father=None,children=[]):

Python оценивает значение по умолчанию [] только один раз (создавая пустой объект list), а затем повторно использует это оцененное значение (ссылку на этот объект list) для всех последующих вызовов этой функции. .

В вашем случае это функция __init__(), которая вызывается каждый раз, когда вы создаете экземпляр класса Node. Если вы создаете экземпляр Node несколько раз без явной передачи третьего аргумента, во всех этих вызовах __init__() параметру children присваивается один и тот же объект list в качестве значения по умолчанию. Вы используете это значение для установки атрибута children всех этих экземпляров. Другими словами, для всех этих экземпляров Node атрибут children будет указывать на один и тот же объект list. Вот почему добавление ребенка к отцу Node также добавляет того же ребенка к текущему Node.

Правильный способ переписать __init__():

class Node(object):
    def __init__(self,value,father=None,children=None):
        self.value=value
        self.father=father
        self.children=children if children is not None else []

Мораль

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

Все это задокументировано здесь

person fountainhead    schedule 13.11.2020