我正在尝试从 python 中的列表构建一棵树。我的树中的节点具有我的列表的索引值,每个节点的父节点将是列表中该索引处指定的节点。
在下面的代码示例中,varlist 将树的节点元素与输入数组 中的值一起存储。 例如,[-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 个子节点,其余为空.有人可以帮我解释一下这是怎么回事吗?
请您参考如下方法:
首先,您需要了解__repr__ 和__str__ 之间的区别。在这种情况下,您正在尝试 represent 您创建的 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]))
一般来说,最好的做法是使用Use a sentinel value to denote an empty list or dictionary:
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])
