python 链接结构 - 将子节点插入节点 A 的父节点也插入到节点 A

Question

我正在尝试使用 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']

如您所见，当我将新插入的节点追加到父亲的子节点列表中时，它也会插入到新节点的子节点列表中。如何解决这个问题？

Answer 1

问题的发生是因为 Python 如何处理函数的可选参数的默认值。

在 class Node(object) 中，您有这一行：

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

Python只计算默认值[]一次（创建一个空的listobject），然后重用该评估值（引用 list object）对于该函数的所有后续调用。

在您的例子中，函数是 __init__() 函数，每次实例化 Node class 时都会调用该函数。如果您多次实例化 Node 而没有显式传递第三个参数，则在 __init__() 的所有这些调用中，参数 children 将被分配 相同的 list object 作为默认值。您正在使用此值来设置所有这些实例的 children 属性。换句话说，对于所有这些 Node 实例，children 属性将指向相同的 list object。这就是为什么将 child 插入“父亲”Node 也会将相同的 child 添加到当前的 Node.

re-write __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 []

道德

这里的一般寓意是，如果您的参数的默认值是可变 object，它可能会引发这样的意外——您不知道的地方，多个引用存储到单个 object，并且通过一个引用对 object 的突变（更改）也将通过其他引用反映（看到）。

这一切都记录在案here

python 链接结构 - 将子节点插入节点 A 的父节点也插入到节点 A

python linked structure - inserting child to node A's parent is also inserting to node A

python

tree

optional-parameters

optional-arguments

道德