python - 创建树时Python中的对象引用问题

Question

我正在尝试从 python 中的列表构造一棵树。我的树中的节点具有列表的索引值，每个节点的父节点将是列表中该索引处指定的节点。
在下面的代码示例中，varlist 将树的节点元素与输入array 中的值一起存储。 例如，输入列表 [-1, 0, 4, 0, 3] 应给出以下树:

  0
 / \
1   3
     \
      4
       \
        2

The way I'm doing this is to first initialize the nodes separately in a list with default parent as None. Then I'm assigning the parent and child as I traverse the array as follows:

class Node1:
    def __init__(self, val, parent, children = []):
        self.val = val
        if parent == -1:
            self.parent = None
        else:
            self.parent = parent
        self.children = children
    def __str__(self):
        return(str(self.val))

def treeHeight(array):
    varlist = [0] * len(array)
    for i in range(len(array)):
        varlist[i] = Node1(i, None)
    for i in range(len(varlist)):
        if array[i] != -1:
            varlist[i].parent = varlist[array[i]]
            varlist[array[i]].children.append(varlist[i])
        else:
            root = varlist[i]
    for i in range(len(array)):
        print(varlist[i].val,varlist[i].parent, varlist[i].children)
    return(None)
if __name__ == '__main__':
    print(treeHeight([-1, 0, 4, 0, 3]))

我得到的输出是这样的:

0 None [<__main__.Node1 object at 0x1041051d0>, <__main__.Node1 object at 0x104105208>, <__main__.Node1 object at 0x104105780>, <__main__.Node1 object at 0x104105cc0>]
1 0 [<__main__.Node1 object at 0x1041051d0>, <__main__.Node1 object at 0x104105208>, <__main__.Node1 object at 0x104105780>, <__main__.Node1 object at 0x104105cc0>]
2 4 [<__main__.Node1 object at 0x1041051d0>, <__main__.Node1 object at 0x104105208>, <__main__.Node1 object at 0x104105780>, <__main__.Node1 object at 0x104105cc0>]
3 0 [<__main__.Node1 object at 0x1041051d0>, <__main__.Node1 object at 0x104105208>, <__main__.Node1 object at 0x104105780>, <__main__.Node1 object at 0x104105cc0>]
4 3 [<__main__.Node1 object at 0x1041051d0>, <__main__.Node1 object at 0x104105208>, <__main__.Node1 object at 0x104105780>, <__main__.Node1 object at 0x104105cc0>]

输出不是我所期望的，因为不知何故，所有节点的 children 列表中有 4 个元素，而我预计其中 2 个有 2 个子节点，其余为空。有人可以帮我解释一下这是怎么回事吗？

Answer 1

首先，你需要知道__repr__和__str__之间的区别。在这种情况下，您尝试表示您创建的Node1对象，因为repr旨在对象的完整字符串表示；而 str 只是返回一个漂亮的字符串用于打印。您实际上应该定义__repr__。在你的例子中，你实现的 __str__ 函数实际上根本没有被使用。

另一件事是，你永远不应该使用可变对象作为 python 函数中的默认参数，这确实是一个不好的做法，因为:

Passing mutable lists or dictionaries as default arguments to a function can have unforeseen consequences. Usually when a programmer uses a list or dictionary as the default argument to a function, the programmer wants the program to create a new list or dictionary every time that the function is called. However, this is not what Python does. The first time that the function is called, Python creates a persistent object for the list or dictionary. Every subsequent time the function is called, Python uses that same persistent object that was created from the first call to the function.

class Node1:
    def __init__(self, val, parent, children = ()): # default argument should be immutable
        self.val = val
        if parent == -1:
            self.parent = None
        else:
            self.parent = parent
        if not isinstance(children, list):
            children = list(children)
        self.children = children
    def __str__(self):
        return(str(self.val))

    def __repr__(self):
        return(str(self.val)) # need to define __repr__

def treeHeight(array):
    varlist = [0] * len(array)
    for i in range(len(array)):
        varlist[i] = Node1(i, None)
    for i in range(len(varlist)):
        if array[i] != -1:
            varlist[i].parent = varlist[array[i]]
            varlist[array[i]].children.append(varlist[i])
        else:
            root = varlist[i]
    for i in range(len(array)):
        print(varlist[i].val,varlist[i].parent, varlist[i].children)
    return(None)
if __name__ == '__main__':
    print('\n\n')
    print(treeHeight([-1, 0, 4, 0, 3]))

通常，最佳实践是使用“使用标记值来表示空列表或字典”:

class Node1:
    def __init__(self, val, parent=None, child=None): # default argument should be immutable
        self.val = val
        self.children= []
        if parent and parent.val != -1:
            self.parent = parent
        else:
            self.parent = None
        if child:
            self.children.append(child)

#    def __str__(self):
#        return(str(self.val))

    def __repr__(self):
        return(str(self.val)) # need to define __repr__

def treeHeight(arr): # array is reverse attribute in python, use arr instead
    varlist = []
    for i in range(len(arr)):
        varlist.append(Node1(i))
    for i in range(len(varlist)):
        if arr[i]!=-1:
            varlist[i].parent = varlist[arr[i]]
            varlist[arr[i]].children.append(varlist[i])
        else:
            root = varlist[i]

    for i in range(len(arr)):
        print(varlist[i].val,varlist[i].parent, varlist[i].children)
    return

if __name__ == '__main__':
    print('\n\n')
    treeHeight([-1, 0, 4, 0, 3])